Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration

DOI10.1007/978-3-642-27660-6_17zbMath1298.05246OpenAlexW1497588846MaRDI QIDQ2891369

Dieter Kratsch, Jean-François Couturier, Pinar Heggernes, Pim van 't Hof

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_17

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

Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ On the number of minimal dominating sets on some graph classes

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• A note on the complexity of the chromatic number problem
• The domatic number problem on some perfect graph families
• Algorithmic graph theory and perfect graphs
• Enumeration of Minimal Dominating Sets and Variants
• Finding Induced Subgraphs via Minimal Triangulations
• Feedback Vertex Sets in Tournaments
• Node-Deletion Problems on Bipartite Graphs
• Graph Classes: A Survey
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Combinatorial bounds via measure and conquer
• On cliques in graphs

This page was built for publication: Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration