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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Weighted Upper Edge Cover: Complexity and Approximability

Thumbnail
Ouvrir
Weighted_Upper.pdf (584.5Kb)
Date
2020
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Complexity; Approximability
Nom de la revue
Journal of Graph Algorithms and Applications
Volume
24
Numéro
2
Date de publication
2020
Pages article
65-68
Nom de l'éditeur
Brown University
DOI
http://dx.doi.org/10.7155/jgaa.00519
URI
https://basepub.dauphine.fr/handle/123456789/20968
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Khoshkhah, Kaveh
Khosravian Ghadikolaei, Mehdi
Monnot, Jérôme
Sikora, Florian
Type
Article accepté pour publication ou publié
Résumé en anglais
Optimization 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.

  • 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

 Cette création est mise à disposition sous un contrat Creative Commons.