• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
http://dx.doi.org/10.1007/978-3-540-74839-7_20
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

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    The Price of Optimum: Complexity and Approximation for a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    Extension and its price for the connected vertex cover problem 
    Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo