Show simple item record

dc.contributor.authorKhoshkhah, Kaveh
dc.contributor.authorKhosravian Ghadikolaei, Mehdi
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorSikora, Florian
dc.date.accessioned2020-09-02T10:58:08Z
dc.date.available2020-09-02T10:58:08Z
dc.date.issued2020
dc.identifier.issn1526-1719
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20968
dc.language.isoenen
dc.subjectComplexity
dc.subjectApproximability
dc.subject.ddc005en
dc.titleWeighted Upper Edge Cover: Complexity and Approximability
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenOptimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such “flipping” of the objective function was done for many classical optimization problems. For example, Minimum Vertex Cover becomes Maximum Minimal Vertex Cover, Maximum Independent Set becomes Minimum Maximal Independent Set and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called Upper Edge Cover, a problem having application in genomic sequence alignment. It is well-known that Minimum Edge Cover is polynomial-time solvable and the “flipped” version is NP-hard, but constant approximable. We show that the weighted Upper Edge Cover is much more difficult than Upper Edge Cover because it is not O(1n1/2−ε) approximable, nor O(1Δ1−ε) in edge-weighted graphs of size n and maximum degree Δ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and k-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.
dc.relation.isversionofjnlnameJournal of Graph Algorithms and Applications
dc.relation.isversionofjnlvol24
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2020
dc.relation.isversionofjnlpages65-68
dc.relation.isversionofdoi10.7155/jgaa.00519
dc.relation.isversionofjnlpublisherBrown University
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2020-12-17T09:12:46Z
hal.person.labIds
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record