Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time

DOI10.1137/1.9781611974782.30zbMath1409.68204arXiv1704.02844OpenAlexW2949936571MaRDI QIDQ4575767

Danupon Nanongkai, Sayan Bhattacharya, Monika R. Henzinger

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Approximation algorithms (68W25)

Related Items (14)

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic clustering to minimize the sum of radii ⋮ Round Compression for Parallel Matching Algorithms ⋮ Dynamic Matching Algorithms in Practice ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Maximum matching on trees in the online preemptive and the incremental graph models

This page was built for publication: Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log³ n) Worst Case Update Time