Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010), Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs, Journal of Discrete Algorithms, 8, 1, p. 36-49. http://dx.doi.org/10.1016/j.jda.2009.01.005
Type
Article accepté pour publication ou publiéExternal document link
http://hal.archives-ouvertes.fr/hal-00178912/en/Date
2010Journal name
Journal of Discrete AlgorithmsVolume
8Number
1Publisher
Elsevier
Pages
36-49
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). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.Subjects / Keywords
Connected vertex cover; Chordal graphs; Bipartite graphs; Planar graphs; Hypergraphs; Approximation algorithmRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
-
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
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Communication / Conférence