• 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

New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set

Thumbnail
Ouvrir
Ipec_EDS.pdf (183.3Kb)
Date
2015
Indexation documentaire
Recherche opérationnelle
Subject
Edge dominating set; Parameterized complexity; Approximation algorithms
Nom de la revue
Theory of Computing Systems
Volume
56
Numéro
2
Date de publication
2015
Pages article
330-346
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/s00224-014-9549-5
URI
https://basepub.dauphine.fr/handle/123456789/13887
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Escoffier, Bruno
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Xiao, Mingyu
94741 School of Computer Science and Engineering
Type
Article accepté pour publication ou publié
Résumé en anglais
An 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.

  • 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.