Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs

Abstract : It was proved independently and with different techniques in [Golovach et al. - ICALP 2013] and [Kanté et al. - ISAAC 2012] that there exists an incremental output polynomial algorithm for the enumeration of the minimal edge dominating sets in graphs, i.e., minimal dominating sets in line graphs. We provide the first polynomial delay and polynomial space algorithm for the problem. We propose a new technique to enlarge the applicability of Berge’s algorithm that is based on skipping hard parts of the enumeration by introducing a new search strategy. The new search strategy is given by a strong use of the structure of line graphs.
Type de document :
Communication dans un congrès
Frank Dehne; Jörg-Rüdiger Sack; Ulrike Stege. Algorithms and Data Structures (WADS), Aug 2015, Victoria, Canada. Springer, Lecture Notes in Computer Science, 9214, pp.446-457
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01248851
Contributeur : Marie-France Sagot <>
Soumis le : mardi 23 mai 2017 - 10:33:36
Dernière modification le : jeudi 28 juin 2018 - 14:36:14

Lien texte intégral

Identifiants

  • HAL Id : hal-01248851, version 1
  • ARXIV : 1404.3501

Citation

Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, Takeaki Uno. Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs . Frank Dehne; Jörg-Rüdiger Sack; Ulrike Stege. Algorithms and Data Structures (WADS), Aug 2015, Victoria, Canada. Springer, Lecture Notes in Computer Science, 9214, pp.446-457. 〈hal-01248851〉

Partager

Métriques

Consultations de la notice

239