On hard instances of approximate vertex cover

DOI10.1145/1435375.1435382zbMath1445.68179OpenAlexW1996249628MaRDI QIDQ4962765

Sundar Vishwanathan

Publication date: 5 November 2018

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

Full work available at URL: https://doi.org/10.1145/1435375.1435382

zbMATH Keywords

approximation algorithmsvertex cover

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) Approximation algorithms (68W25)

Related Items (1)

The complexity of König subgraph problems and above-guarantee vertex cover

This page was built for publication: On hard instances of approximate vertex cover