Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Type: Preprint

Publication Date: 2018-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.1806.10051

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time	2019	Soheil Behnezhad Mahsa Derakhshan MohammadTaghi Hajiaghayi Clifford Stein Madhu Sudan
+	Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time	2019	Shiri Chechik Tianyi Zhang
+	Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time	2019	Shiri Chechik Tianyi Zhang
+	Improved Algorithms for Fully Dynamic Maximal Independent Set	2018	Yuhao Du Hengjie Zhang
+	Fully Dynamic Maximal Independent Set with Sublinear Update Time	2018	Sepehr Assadi Krzysztof Onak Baruch Schieber Shay Solomon
+	Fully Dynamic MIS in Uniformly Sparse Graphs	2018	Krzysztof Onak Baruch Schieber Shay Solomon Nicole Wein
+	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time	2019	Soheil Behnezhad Mahsa Derakhshan Hajiaghayi MohammadTaghi Stein Cliff Madhu Sudan
+ PDF Chat	Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time	2019	Shiri Chechik Tianyi Zhang
+ PDF Chat	Fully Dynamic Maximal Matching in $O(\log n)$ Update Time	2015	Surender Baswana Manoj Gupta Sandeep Sen
+	Dynamic Maximal Independent Set	2019	Morteza Monemizadeh
+ PDF Chat	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2015	Ofer Neiman Shay Solomon
+ PDF Chat	Fully Dynamic Maximal Matching in O (log n) Update Time	2011	Surender Baswana Manoj Gupta Sandeep Sen
+	Dynamic Maximal Independent Set.	2019	Morteza Monemizadeh
+ PDF Chat	Fully Dynamic MIS in Uniformly Sparse Graphs	2020	Krzysztof Onak Baruch Schieber Shay Solomon Nicole Wein
+	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2012	Ofer Neiman Shay Solomon
+	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2012	Ofer Neiman Shay Solomon
+	Fully dynamic maximal matching in O(log n) update time	2011	Surender Baswana Manoj Gupta Sandeep Sen
+	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+ PDF Chat	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Optimal Fully Dynamic <i>k</i>-Center Clustering for Adaptive and Oblivious Adversaries	2023	MohammadHossein Bateni Hossein Esfandiari Hendrik Fichtenberger Monika Henzinger Rajesh Jayaram Vahab Mirrokni Andreas Wiese

Works Cited by This (0)

Action	Title	Year	Authors