Complexity and Approximation Results for the Connected Vertex Cover Problem
- 6 December 2007
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC
Abstract
No abstract availableThis publication has 16 references indexed in Scilit:
- Approximation Schemes for First-Order Definable Optimisation ProblemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree CoverLecture Notes in Computer Science, 2006
- Parameterized Complexity of Generalized Vertex Cover ProblemsLecture Notes in Computer Science, 2005
- Some APX-completeness results for cubic graphsTheoretical Computer Science, 2000
- Graph Classes: A SurveyPublished by Society for Industrial & Applied Mathematics (SIAM) ,1999
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 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 graphsPublished by Association for Computing Machinery (ACM) ,1982
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977