Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

DOI10.1137/1.9781611975482.116zbMath1432.68333arXiv1806.10051OpenAlexW4235082106MaRDI QIDQ5236302

Krzysztof Onak, Sepehr Assadi, Shay Solomon, Baruch Schieber

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

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) Randomized algorithms (68W20)

Related Items (4)

Unnamed Item ⋮ 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 in n Update Time