A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
Mamadou Moustapha Kanté
1
Vincent Limouzy
2
Arnaud Mary
3
Lhouari Nourine
4
Takeaki Uno
5
3
ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
Inria Grenoble - Rhône-Alpes
Mamadou Moustapha Kanté 1
Mail :
Author IdHAL : makante arXiv : https://arxiv.org/a/kante ORCID : https://orcid.org/0000-0003-1838-7744
Vincent Limouzy 2
Mail :
Author IdHAL : vincent-limouzy
Arnaud Mary 3
Mail :
Author IdHAL : arnaud-mary
Lhouari Nourine 4
Mail :
Author
Takeaki Uno 5
Author
1
LaBRI - Laboratoire Bordelais de Recherche en Informatique (Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5800 (France)
- École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) (France)
- Université Sciences et Technologies - Bordeaux 1 (351 cours de la Libération - 33405 Talence cedex - France)
- Université Bordeaux Segalen - Bordeaux 2 (146 rue Léo Saignat - 33076 Bordeaux cedex - France)
2
LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (Bât ISIMA / Campus des Cézeaux BP 10025 / 63173 Aubière Cedex - France)
- Ecole Nationale Supérieure des Mines de St Etienne : UMR6158 (France)
- UCA - Université Clermont Auvergne : UMR6158 (49, bd François-Mitterrand / CS 60032 / 63001 Clermont-Ferrand Cedex 1 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6158 (France)
3
ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (Université Claude Bernard (Lyon 1),
Campus DOUA
43, Boulevard du 11 Novembre 1918
69622 Villeurbanne cedex - France)
- Inria Grenoble - Rhône-Alpes (Inovallée
655 avenue de l'Europe
38330 Montbonnot - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
4
LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex - France)
- UBP - Université Blaise Pascal - Clermont-Ferrand 2 : UMR6158 (34, avenue Carnot - BP 185 / 63006 Clermont-Ferrand cedex - France)
- UdA - Université d'Auvergne - Clermont-Ferrand I (49, Boulevard François-Mitterrand / CS 60032 / 63001 Clermont-Ferrand Cedex 1 - France)
- Sigma CLERMONT - Sigma CLERMONT (Sigma CLERMONT Campus des Cézeaux CS 20265 63178 Aubière Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6158 (France)
- Ecole Nationale Supérieure des Mines de St Etienne : UMR6158 (France)
5
NII - National Institute of Informatics (2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430 - Japan)
Document type :
Book sections
Complete list of metadatas
https://hal.uca.fr/hal-02082337
Contributor : Vincent Limouzy <>
Submitted on : Thursday, March 28, 2019 - 11:02:25 AM
Last modification on : Wednesday, March 4, 2020 - 12:28:03 PM
Contributor : Vincent Limouzy <>
Submitted on : Thursday, March 28, 2019 - 11:02:25 AM
Last modification on : Wednesday, March 4, 2020 - 12:28:03 PM
Links full text
Identifiers
- HAL Id : hal-02082337, version 1
- DOI : 10.1007/978-3-662-53174-7_11
Collections
PRES_CLERMONT | CNRS | LIMOS | LABRI | SIGMA-CLERMONT | INRIA | UNIV-BORDEAUX
Citation
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, Takeaki Uno. A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs. WG 2015: Graph-Theoretic Concepts in Computer Science, pp.138-153, 2016, ⟨10.1007/978-3-662-53174-7_11⟩. ⟨hal-02082337⟩
Metrics
Record views
