Fully dynamic maximal independent set with sublinear update time

DOI10.1145/3188745.3188922zbMath1427.68224arXiv1802.09709OpenAlexW2963645943WikidataQ130879177 ScholiaQ130879177MaRDI QIDQ5230340

Baruch Schieber, Shay Solomon, Sepehr Assadi, Krzysztof Onak

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.09709

zbMATH Keywords

maximal independent setdynamic graph algorithmsdynamic distributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (5)

Unnamed Item ⋮ Trade-offs in dynamic coloring for bipartite and general graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time

This page was built for publication: Fully dynamic maximal independent set with sublinear update time