Enumeration of minimal connected dominating sets for chordal graphs

DOI10.1016/J.DAM.2019.07.015MaRDI QIDQ2174551zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Dieter Kratsch, Reza Saei, Petr A. Golovach

Publication date 21 April 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.07.015

zbMATH Keywords

enumerationchordal graphsminimal connected dominating sets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• Enumerating minimal dominating sets in chordal graphs
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• Algorithmic graph theory and perfect graphs
• An exact algorithm for connected red-blue dominating set
• Below all subsets for minimal connected dominating set
• Combinatorial bounds via measure and conquer
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal graphs
• Enumerating minimal subset feedback vertex sets
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• Exact algorithms for graph homomorphisms
• Exact exponential algorithms.
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in interval graphs and trees
• On cliques in graphs
• On the enumeration of minimal dominating sets and related notions
• On the number of minimal dominating sets on some graph classes
• The maximum number of minimal dominating sets in a tree

Cited in

(14)

• Locally definable vertex set properties are efficiently enumerable
• Enumeration of minimal tropical connected sets
• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Enumerating minimal dominating sets in chordal graphs
• Enumerating Minimal Tropical Connected Sets
• Enumerating minimal defensive alliances
• Below all subsets for minimal connected dominating set
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• An improved exact algorithm for minimum dominating set in chordal graphs

This page was built for publication: Enumeration of minimal connected dominating sets for chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174551)