Fully dynamic maximal independent set with polylogarithmic update time

DOI10.1109/FOCS.2019.00032MaRDI QIDQ6944205zbMATH OpenFDO

Authors Mohammad T. Hajiaghayi, Mahsa Derakhshan, Soheil Behnezhad, Madhu Sudan, Clifford Stein

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00032

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(6)

• Fast deterministic algorithms for highly-dynamic networks
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• Deterministic rounding of dynamic fractional matchings
• Fitting tree metrics and ultrametrics in data streams
• Minimizing recourse in an adaptive balls and bins game

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

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