• 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

Extension and its price for the connected vertex cover problem

Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019), Extension and its price for the connected vertex cover problem, in Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia, Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings, Springer : Berlin Heidelberg, p. 315-326. 10.1007/978-3-030-25005-8_26

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-02344051
Date
2019
Conference title
Combinatorial Algorithms 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, Proceedings
Conference date
2019
Conference city
Berlin Heidelberg
Conference country
ITALY
Book title
Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings
Book author
Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-030-25004-1
Pages
315-326
Publication identifier
10.1007/978-3-030-25005-8_26
Metadata
Show full item record
Author(s)
Khosravian Ghadikolaei, Mehdi
Melissinos, Nikolaos
Monnot, Jérôme
Pagourtzis, Aris
Abstract (EN)
We consider extension variants of Vertex Cover and Independent Set, following a line of research initiated in [9]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G=(V,E) and a vertex set U⊆V , does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S, such that U⊆S (respectively, U⊇S ). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC, that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE), a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs.
Subjects / Keywords
extension problems; connected vertex cover; upper con- nected vertex cover; price of extension; special graph classes; approxima- tion algorithms; NP-completeness

Related items

Showing items related by title and author.

  • Thumbnail
    On the Complexity of the Upper r-Tolerant Edge Cover Problem 
    Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2020) Communication / Conférence
  • Thumbnail
    Extension of Vertex Cover and Independent Set in Some Classes of Graphs 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    Extension of Some Edge Graph Problems: Standard and Parameterized Complexity 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    On the complexity of solution extension of optimization problems 
    Sikora, Florian; Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme (2020) Article accepté pour publication ou publié
  • 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é
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