2026-07-22T11:56:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11559 2024-03-06T10:48:18Z ddc:004 open_access

Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs Defrain, Oscar Nourine, Lhouari Minimal dominating sets enumeration algorithms linear delay enumeration chordal graphs forbidden induced paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oscar Defrain and Lhouari Nourine 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.63 urn:nbn:de:0030-drops-115591 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.63 eng https://creativecommons.org/licenses/by/3.0/legalcode