Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
Authors:
- 1 March 2010
- journal article
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 8 (1) , 36-49
Abstract
No abstract availableKeywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Complexity of approximating bounded variants of optimization problemsTheoretical Computer Science, 2005
- A new multilayered PCP and the hardness of hypergraph vertex cover2003
- Local search for the minimum label spanning tree problem with bounded color classesOperations Research Letters, 2003
- Some APX-completeness results for cubic graphsTheoretical Computer Science, 2000
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 1998
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Approximating the tree and tour covers of a graphInformation Processing Letters, 1993
- On approximating a vertex cover for planar graphs1982
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977