Show simple item record

dc.contributor.authorEscoffier, Bruno*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorPaschos, Vangelis*
dc.contributor.authorXiao, Mingyu*
dc.date.accessioned2014-08-29T07:04:15Z
dc.date.available2014-08-29T07:04:15Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13887
dc.language.isoenen
dc.subjectEdge dominating seten
dc.subjectParameterized complexityen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleNew Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Seten
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenAn edge dominating set in a graph G = (V, E) is a subset S of edges such that each edge in E − S is adjacent to at least one edge in S. The edge dominating set problem, to find an edge dominating set of minimum size, is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. In this paper, we present improved hardness results and parameterized approximation algorithms for edge dominating set. More precisely, we first show that it is NP-hard to approximate edge dominatingset in polynomial time within a factor better than 1.18. Next, we give a parameterized approximation schema (with respect to the standard parameter) for the problem and, finally, we develop an O ∗(1.821 τ )-time exact algorithm where τ is the size of a minimum vertex cover of G.en
dc.relation.isversionofjnlnameTheory of Computing Systems
dc.relation.isversionofjnlvol56
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages330-346
dc.relation.isversionofdoi10.1007/s00224-014-9549-5en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds94741*
hal.faultCode{"duplicate-entry":{"hal-01200585":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record