Fully Dynamic MIS in Uniformly Sparse Graphs

DOI10.1145/3378025zbMath1484.68169OpenAlexW3011393812MaRDI QIDQ4987444

Shay Solomon, Nicole Wein, Krzysztof Onak, Baruch Schieber

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

maximal independent setdynamic graph algorithmsedge orientationsgraph arboricity

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)

This page was built for publication: Fully Dynamic MIS in Uniformly Sparse Graphs