Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time

DOI10.1137/1.9781611975482.113zbMath1432.68339arXiv1805.03498OpenAlexW4229488000MaRDI QIDQ5236297

Janardhan Kulkarni, Sayan Bhattacharya

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/1805.03498

Mathematics Subject Classification ID

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

Related Items (3)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Constant-time dynamic weight approximation for minimum spanning forest

This page was built for publication: Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊²) Amortized Update Time