English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In [M. M. Kant\'e, V. Limouzy, A. Mary, and L. Nourine. On the enumeration ofminimal dominating sets and related notions. SIAM Journal on DiscreteMathematics, 28(4):1916-1929, 2014] the authors give an $O(n+m)$ delayalgorithm based on neighborhood inclusions for the enumeration of minimaldominating sets in split and $P_6$-free chordal graphs. In this paper, weinvestigate generalizations of this technique to $P_k$-free chordal graphs forlarger integers $k$. In particular, we give $O(n+m)$ and $O(n^3\cdot m)$ delaysalgorithms in the classes of $P_7$-free and $P_8$-free chordal graphs. As for$P_k$-free chordal graphs for $k\geq 9$, we give evidence that such a techniqueis inefficient as a key step of the algorithm, namely the irredundant extensionproblem, becomes NP-complete.

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