Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.63
URN: urn:nbn:de:0030-drops-115591
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11559/
Defrain, Oscar ; Nourine, Lhouari
Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs
| pdf-format: |
|
Abstract
In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916-1929, 2014.] the authors give an O(n+m) delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and P_6-free chordal graphs. In this paper, we investigate generalizations of this technique to P_k-free chordal graphs for larger integers k. In particular, we give O(n+m) and O(n^3 * m) delays algorithms in the classes of P_7-free and P_8-free chordal graphs. As for P_k-free chordal graphs for k >= 9, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.
BibTeX - Entry
@InProceedings{defrain_et_al:LIPIcs:2019:11559,
author = {Oscar Defrain and Lhouari Nourine},
title = {{Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {63:1--63:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11559},
URN = {urn:nbn:de:0030-drops-115591},
doi = {10.4230/LIPIcs.ISAAC.2019.63},
annote = {Keywords: Minimal dominating sets, enumeration algorithms, linear delay enumeration, chordal graphs, forbidden induced paths}
}
| Keywords: | Minimal dominating sets, enumeration algorithms, linear delay enumeration, chordal graphs, forbidden induced paths | |
| Seminar: | 30th International Symposium on Algorithms and Computation (ISAAC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 28.11.2019 |
