Show simple item record

hal.structure.identifier
dc.contributor.authorKhoshkhah, Kaveh*
hal.structure.identifier
dc.contributor.authorKhosravian Ghadikolaei, Mehdi*
hal.structure.identifier
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
*
hal.structure.identifier
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2019-07-16T09:59:51Z
dc.date.available2019-07-16T09:59:51Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19240
dc.language.isoenen
dc.subjectMaximum minimal edge cover
dc.subjectGraph optimization problem
dc.subjectComputational complexity
dc.subjectApproximability
dc.subject.ddc005en
dc.titleWeighted Upper Edge Cover: Complexity and Approximability
dc.typeCommunication / Conférence
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.identifier.citationpages235-247
dc.relation.ispartoftitleWALCOM: Algorithms and Computation
dc.relation.ispartofeditorGautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya, Shin-ichi Nakano
dc.relation.ispartofpublnameSpringer International Publishing
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofurl10.1007/978-3-030-10564-8
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-030-10563-1;978-3-030-10564-8
dc.relation.confdate2019
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-10564-8_19
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-04-03T13:33:32Z
hal.identifierhal-02184878*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record