Enumerating minimal connected dominating sets in graphs of bounded chordality
From MaRDI portal
Publication:278724
DOI10.1016/j.tcs.2016.03.026zbMath1339.05190OpenAlexW2321590673MaRDI QIDQ278724
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Publication date: 2 May 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.03.026
Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Related Items (8)
Linear-Time Generation of Random Chordal Graphs ⋮ On the number of connected sets in bounded degree graphs ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph ⋮ Below All Subsets for Minimal Connected Dominating Set
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Enumerating minimal subset feedback vertex sets
- On the number of minimal dominating sets on some graph classes
- Exact exponential algorithms.
- An exact algorithm for connected red-blue dominating set
- Enumerating maximal independent sets with applications to graph colouring.
- Minimal triangulations of graphs: a survey
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Characterizations of strongly chordal graphs
- Distance-hereditary graphs
- Algorithmic graph theory and perfect graphs
- Subset feedback vertex sets in chordal graphs
- Exact algorithms for graph homomorphisms
- Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
- On the Number of Minimal Separators in Graphs
- Connecting Terminals and 2-Disjoint Connected Subgraphs
- Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
- Large Induced Subgraphs via Triangulations and CMSO
- Characterizations of totally balanced matrices
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Graph Classes: A Survey
- Asteroidal Triple-Free Graphs
- Feedback Vertex Sets in Tournaments
- Combinatorial bounds via measure and conquer
- On the Enumeration of Minimal Dominating Sets and Related Notions
- On cliques in graphs
This page was built for publication: Enumerating minimal connected dominating sets in graphs of bounded chordality
