Fully dynamic maximal independent set with sublinear update time
Authors:
Open Access
- 20 June 2018
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 815-826
Abstract
No abstract availableKeywords
All Related Versions
This publication has 31 references indexed in Scilit:
- On Dynamic Shortest Paths ProblemsAlgorithmica, 2010
- A new approach to dynamic all pairs shortest pathsJournal of the ACM, 2004
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Randomized fully dynamic graph algorithms with polylogarithmic time per operationJournal of the ACM, 1999
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- An overview of computational complexityCommunications of the ACM, 1983
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981