Improved Algorithms for Fully Dynamic Maximal Independent Set

2018/04/24 by Yuhao Du, Du, Yuhao, Hengjie Zhang +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1804.08908

openalex publication_date 2018/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Maintaining maximal independent set in dynamic graph is a fundamental open problem in graph theory and the first sublinear time deterministic algorithm was came up by Assadi, Onak, Schieber and Solomon(STOC'18), which achieves O(m^3/4) amortized update time. We have two main contributions in this paper. We present a new simple deterministic algorithm with O(m^2/3√(log m)) amortized update time, which improves the previous best result. And we also present the first randomized algorithm with expected O(√(m)log^1.5m) amortized time against an oblivious adversary.

Cited by

• Dynamic Maximal Independent Set

Related

• Fully Dynamic Maximal Independent Set with Sublinear Update Time
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
• Simple dynamic algorithms for Maximal Independent Set and other problems
• Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time