Enumerating minimal dominating sets in chordal graphs
From MaRDI portal
Publication:738877
DOI10.1016/j.ipl.2016.07.002zbMath1371.05127OpenAlexW2487741757MaRDI QIDQ738877
Faisal N. Abu-Khzam, Pinar Heggernes
Publication date: 16 August 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2016.07.002
graph algorithmschordal graphsbranching algorithminput sensitive enumerationmaximum number of minimal dominating sets
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 (10)
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Linear-Time Generation of Random Chordal Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Bounds for the connected domination number of maximal outerplanar graphs ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Acyclic edge coloring of chordal graphs with bounded degree ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs
Cites Work
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- On the number of minimal dominating sets on some graph classes
- Exact exponential algorithms.
- On rigid circuit graphs
- Algorithmic graph theory and perfect graphs
- Graph Classes: A Survey
- On the Enumeration of Minimal Dominating Sets and Related Notions
This page was built for publication: Enumerating minimal dominating sets in chordal graphs