A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
From MaRDI portal
Publication:5236301
DOI10.1137/1.9781611975482.115zbMath1432.68338arXiv1810.10932OpenAlexW2898134584MaRDI QIDQ5236301
Aaron Bernstein, Sebastian Forster, Monika R. Henzinger
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.10932
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20)
Related Items
Upper and lower bounds for fully retroactive graph problems ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review
