A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching

DOI10.1145/3469833MaRDI QIDQ5035873zbMATH OpenOpenAlexFDO

Authors Aaron Bernstein, Sebastian Forster, Monika R. Henzinger

Publication date 22 February 2022

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

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

zbMATH Keywords

maximal matchingspanners

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A deamortization approach for dynamic spanner and dynamic maximal matching
• Fully dynamic spanners with worst-case update time
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier

This page was built for publication: A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching

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