• 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 - No 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), 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
2010
Journal name
Journal of Discrete Algorithms
Volume
8
Number
1
Publisher
Elsevier
Pages
36-49
Publication identifier
http://dx.doi.org/10.1016/j.jda.2009.01.005
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Gourvès, Laurent
Escoffier, Bruno
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). 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 algorithm

Related items

Showing items related by title and author.

  • 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
    Complexity and approximation results for the connected vertex cover problem 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
  • 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
    On the impact of local taxes in a set cover game 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) 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