Minimal dominating sets in graph classes: combinatorial bounds and enumeration

DOI10.1016/j.tcs.2013.03.026zbMath1283.05200OpenAlexW2093334671MaRDI QIDQ387008

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

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.026

zbMATH Keywords

graph classesminimal dominating setscombinatorial boundsenumeration algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (22)

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Completion and decomposition of hypergraphs into dominating sets of graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Minimum Dominating Set for the Prism Graph Family ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ Minimum cost flow problem with conflicts ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Enumerating Minimal Tropical Connected Sets ⋮ On the number of minimal dominating sets on some graph classes ⋮ Domination cover number of graphs ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Enumerating minimal dominating sets in chordal graphs ⋮ Linear-time algorithm for generating c-isolated bicliques ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs

Cites Work

• Unnamed Item
• 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
• Threshold graphs and related topics
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Optimal greedy algorithms for indifference graphs
• Trees having many minimal dominating sets
• Incidence matrices and interval graphs
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Enumeration of Minimal Dominating Sets and Variants
• Finding Induced Subgraphs via Minimal Triangulations
• The Comparability Graph of a Tree
• Node-Deletion Problems on Bipartite Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph Classes: A Survey
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs
• Feedback Vertex Sets in Tournaments
• On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
• Combinatorial bounds via measure and conquer
• Enumerating Minimal Subset Feedback Vertex Sets
• On cliques in graphs

This page was built for publication: Minimal dominating sets in graph classes: combinatorial bounds and enumeration