• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Extension of Some Edge Graph Problems: Standard and Parameterized Complexity

Thumbnail
View/Open
fct_19.pdf (389.0Kb)
Date
2019
Notes
Le PDF est une version auteur non publiée.
Dewey
Recherche opérationnelle
Sujet
Extension problems; Edge cover; Matching; Edge domination; NP-completeness; Parameterized complexity; Approximation
DOI
http://dx.doi.org/10.1007/978-3-030-25027-0_13
Conference date
2019
Book title
Fundamentals of Computation Theory: 22nd International Symposium, FCT 2019
Author
Leszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
Publisher
Springer International Publishing
Publisher city
Berlin Heidelberg
ISBN
978-3-030-25026-3;978-3-030-25027-0
Book URL
10.1007/978-3-030-25027-0
URI
https://basepub.dauphine.fr/handle/123456789/20064
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Casel, Katrin
84008 FB IV, Universität Trier, D-54286 Trier, Allemagne
264735 Hasso Plattner Institute (HPI)
Fernau, Henning
84008 FB IV, Universität Trier, D-54286 Trier, Allemagne
Khosravian Ghadikolaei, Mehdi
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
185-200
Abstract (EN)
We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph G=(V,E) and an edge set U⊆E, it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution E′ which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set U (resp., avoiding any edges from the forbidden edge set E∖U). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.