Enumerating minimal connected dominating sets in graphs of bounded chordality

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

zbMATH Keywords

enumerationexact exponential algorithmsminimal connected dominating sets

Mathematics Subject Classification ID

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