Fully dynamic MIS in uniformly sparse graphs

DOI10.1145/3378025MaRDI QIDQ4987444zbMATH OpenOpenAlexFDO

Authors Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9096/

zbMATH Keywords

dynamic graph algorithmsedge orientationsgraph arboricitymaximal independent set

Mathematics Subject Classification ID

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

Recommendations

• Fully dynamic MIS in uniformly sparse graphs
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Fully dynamic maximal independent set with sublinear update time
• Fully dynamic maximal matching in O( n) update time
• Fully dynamic arboricity maintenance

Cited in

(3)

• All maximal independent sets and dynamic dominance for sparse graphs
• Fully dynamic MIS in uniformly sparse graphs
• Local density and its distributed approximation

This page was built for publication: Fully dynamic MIS in uniformly sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987444)