Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

DOI10.1137/1.9781611973402.124zbMath1421.68203OpenAlexW2477603932MaRDI QIDQ5384086

Michel X. Goemans, Sam Chiu-wai Wong, Wang-Chi Cheung

Publication date: 20 June 2019

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

Full work available at URL: https://doi.org/10.1137/1.9781611973402.124

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Tight approximation for partial vertex cover with hard capacities ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Parameterized certificate dispersal and its variants

This page was built for publication: Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs