Thumbnail - Request a copy

Complexity and approximation results for the connected vertex cover problem

Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007), Complexity and approximation results for the connected vertex cover problem, in Brandstädt, Andreas; Kratsch, Dieter; Müller, Haiko, Graph-Theoretic Concepts in Computer Science. 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, Springer : Berlin, p. 202-213. http://dx.doi.org/10.1007/978-3-540-74839-7_20

Type
Communication / Conférence
Date
2007
Conference title
WG'07 33rd International Workshop on Graph-Theoretic Concepts in Computer Science
Conference date
2007-06
Conference city
Dornburg
Conference country
Allemagne
Book title
Graph-Theoretic Concepts in Computer Science. 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers
Book author
Brandstädt, Andreas; Kratsch, Dieter; Müller, Haiko
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4769
Published in
Berlin
ISBN
978-3-540-74838-0
Number of pages
341
Pages
202-213
Publication identifier
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Gourvès, Laurent
Monnot, Jérôme cc
Abstract (EN)
We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs).
Subjects / Keywords
approximation algorithm; APX-complete; planar graphs; bipartite graphs; chordal graphs; Connected vertex cover