A dynamic algorithm maintains a maximal independent set in an edge-update stream with amortized O(log^3 n) update time.
Improved Algorithms for Fully Dynamic Maximal Independent Set
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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}\sqrt{\log m})$ amortized update time, which improves the previous best result. And we also present the first randomized algorithm with expected $O(\sqrt{m}\log^{1.5}m)$ amortized time against an oblivious adversary.
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
A parallel batch-dynamic algorithm maintains a lexicographically-first maximal independent set with O(b log^3 n) expected work and polylog depth, outperforming prior sequential dynamic algorithms even for single updates.
citing papers explorer
-
Dynamic Maximal Independent Set
A dynamic algorithm maintains a maximal independent set in an edge-update stream with amortized O(log^3 n) update time.
-
Parallel Batch-Dynamic Maximal Independent Set
A parallel batch-dynamic algorithm maintains a lexicographically-first maximal independent set with O(b log^3 n) expected work and polylog depth, outperforming prior sequential dynamic algorithms even for single updates.