Fully dynamic maximal independent set in expected poly-log update time

DOI10.1109/FOCS.2019.00031MaRDI QIDQ6944206zbMATH OpenFDO

Authors Shiri Chechik, Tianyi Zhang

Publication date 12 August 2025

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

Mathematics Subject Classification ID

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

Cited in

(3)

• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• Minimizing recourse in an adaptive balls and bins game

This page was built for publication: Fully dynamic maximal independent set in expected poly-log update time

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