Minimal dominating sets in graph classes: combinatorial bounds and enumeration
From MaRDI portal
Publication:387008
DOI10.1016/J.TCS.2013.03.026zbMATH Open1283.05200OpenAlexW2093334671MaRDI QIDQ387008FDOQ387008
Authors: Jean-François Couturier, Pinar Heggernes, Pim Van 't Hof, Dieter Kratsch 
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
Recommendations
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Enumerating minimal dominating sets in chordal graphs
- On the number of minimal dominating sets on some graph classes
- On maximum number of minimal dominating sets in graphs
- Enumeration and maximum number of minimal dominating sets for chordal graphs
Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Exact exponential algorithms.
- 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
- Incidence matrices and interval graphs
- Title not available (Why is that?)
- On cliques in graphs
- The Comparability Graph of a Tree
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
- Node-Deletion Problems on Bipartite Graphs
- Feedback vertex sets in tournaments
- Combinatorial bounds via measure and conquer
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Algorithmic Aspects of Vertex Elimination on Graphs
- An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- Finding induced subgraphs via minimal triangulations
- Enumeration of minimal dominating sets and variants
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- A note on the complexity of the chromatic number problem
- Trees having many minimal dominating sets
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- The domatic number problem on some perfect graph families
- A faster algorithm for dominating set analyzed by the potential method
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- An exact algorithm for subset feedback vertex set on chordal graphs
- Enumerating minimal subset feedback vertex sets
Cited In (33)
- Locally definable vertex set properties are efficiently enumerable
- Title not available (Why is that?)
- Elimination properties for minimal dominating sets of graphs
- Exact solution algorithms for the maximum flow problem with additional conflict constraints
- Combinatorial bounds via measure and conquer
- Linear-time algorithm for generating c-isolated bicliques
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Title not available (Why is that?)
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Domination cover number of graphs
- On the number of minimal dominating sets on some graph classes
- Minimal Roman dominating functions: extensions and enumeration
- Enumeration of maximal irredundant sets for claw-free graphs
- Enumeration of maximal irredundant sets for claw-free graphs
- Enumeration and maximum number of minimal connected vertex covers in graphs
- Enumerating minimal dominating sets in chordal graphs
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- On maximum number of minimal dominating sets in graphs
- On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
- Minimum cost flow problem with conflicts
- Completion and decomposition of hypergraphs into dominating sets of graphs
- Enumerating Minimal Tropical Connected Sets
- Enumeration of minimal connected dominating sets for chordal graphs
- Minimum Dominating Set for the Prism Graph Family
- Minimal dominating sets in interval graphs and trees
- Enumeration and maximum number of minimal dominating sets for chordal graphs
- An improved exact algorithm for minimum dominating set in chordal graphs
- Algorithms and Computation
- Maximum weight perfect matching problem with additional disjunctive conflict constraints
- On the minimum vertex covering transversal dominating sets in graphs and their classification
- Minimal Roman dominating functions: extensions and enumeration
- Constructing the minimum dominating sets of generalized de Bruijn digraphs
- On the enumeration of minimal non-pairwise compatibility graphs
This page was built for publication: Minimal dominating sets in graph classes: combinatorial bounds and enumeration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q387008)
