Enumerating minimal dominating sets in chordal graphs

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

zbMATH Keywords

graph algorithmschordal graphsbranching algorithminput sensitive enumerationmaximum number of minimal dominating sets

Mathematics Subject Classification ID

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