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érenceDate
2007Conference title
WG'07 33rd International Workshop on Graph-Theoretic Concepts in Computer ScienceConference date
2007-06Conference city
DornburgConference country
AllemagneBook title
Graph-Theoretic Concepts in Computer Science. 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised PapersBook author
Brandstädt, Andreas; Kratsch, Dieter; Müller, HaikoPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
4769Published in
Berlin
ISBN
978-3-540-74838-0
Number of pages
341Pages
202-213
Publication identifier
Metadata
Show full item recordAbstract (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 coverRelated items
Showing items related by title and author.
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
-
Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence