On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs

DOI10.1007/978-3-642-45030-3_32zbMath1407.05222OpenAlexW208146514MaRDI QIDQ2872098

Lhouari Nourine, Mamadou Moustapha Kanté, Takeaki Uno, Arnaud Mary, Vincent Limouzy

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45030-3_32

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Counting minimal transversals of \(\beta\)-acyclic hypergraphs ⋮ On the number of minimal dominating sets on some graph classes ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

This page was built for publication: On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs