Neighborhood inclusions for minimal dominating sets enumeration: linear and polynomial delay algorithms in P₇-free and P₈-free chordal graphs

DOI10.4230/LIPICS.ISAAC.2019.63arXiv1805.02412MaRDI QIDQ6301255FDOQ6301255

Lhouari Nourine, Oscar Defrain

Publication date: 7 May 2018

Abstract: In [M. M. Kant'e, 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}cdotm)$ delays algorithms in the classes of $P_7$-free and $P_8$-free chordal graphs. As for $P_k$-free chordal graphs for $kgeq9$, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Neighborhood inclusions for minimal dominating sets enumeration: linear and polynomial delay algorithms in $P_7$-free and $P_8$-free chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301255)