Enumerating minimal dominating sets in chordal graphs

DOI10.1016/J.IPL.2016.07.002MaRDI QIDQ738877zbMATH OpenOpenAlexFDO

Authors 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

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• Enumeration and maximum number of minimal dominating sets for chordal graphs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Enumeration of minimal connected dominating sets for chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality

Cites work

• Algorithmic graph theory and perfect graphs
• Exact exponential algorithms.
• Graph Classes: A Survey
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On rigid circuit graphs
• On the enumeration of minimal dominating sets and related notions
• On the number of minimal dominating sets on some graph classes

Cited in

(18)

• scientific article; zbMATH DE number 1796975 (Why is no real title available?)
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• scientific article; zbMATH DE number 7650296 (Why is no real title available?)
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Enumeration of maximal irredundant sets for claw-free graphs
• Minimal Roman dominating functions: extensions and enumeration
• Enumeration of maximal irredundant sets for claw-free graphs
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• Bounds for the connected domination number of maximal outerplanar graphs
• Enumeration of minimal connected dominating sets for chordal graphs
• Acyclic edge coloring of chordal graphs with bounded degree
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• An improved exact algorithm for minimum dominating set in chordal graphs
• Linear-time generation of random chordal graphs
• scientific article; zbMATH DE number 1107728 (Why is no real title available?)
• Minimal Roman dominating functions: extensions and enumeration

This page was built for publication: Enumerating minimal dominating sets in chordal graphs

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