Show simple item record

dc.contributor.authorCasel, Katrin*
dc.contributor.authorFernau, Henning*
dc.contributor.authorKhosravian Ghadikolaei, Mehdi*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorSikora, Florian*
dc.date.accessioned2019-10-10T11:07:04Z
dc.date.available2019-10-10T11:07:04Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20064
dc.descriptionLe PDF est une version auteur non publiée.
dc.language.isoenen
dc.subjectExtension problems
dc.subjectEdge cover
dc.subjectMatching
dc.subjectEdge domination
dc.subjectNP-completeness
dc.subjectParameterized complexity
dc.subjectApproximation
dc.subject.ddc003en
dc.titleExtension of Some Edge Graph Problems: Standard and Parameterized Complexity
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.
dc.identifier.citationpages185-200
dc.relation.ispartoftitleFundamentals of Computation Theory: 22nd International Symposium, FCT 2019
dc.relation.ispartofeditorLeszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
dc.relation.ispartofpublnameSpringer International Publishing
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofurl10.1007/978-3-030-25027-0
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-030-25026-3;978-3-030-25027-0
dc.relation.confdate2019
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-25027-0_13
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-04-03T13:32:57Z
hal.person.labIds84008$$$264735*
hal.person.labIds84008*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-02310662*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record