Below all subsets for minimal connected dominating set

DOI10.1137/17M1138753MaRDI QIDQ4683902zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh

Publication date 26 September 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.00840

zbMATH Keywords

enumerationconnected dominating set\(2^n\) barrier

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Abstract: A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not contained in $S$ has a neighbor in $S$. A dominating set $S$ is a connected dominating set if the subgraph $G[S]$ induced by $S$ is connected. A connected dominating set $S$ is a minimal connected dominating set if no proper subset of $S$ is also a connected dominating set. We prove that there exists a constant $varepsilon>10^{-50}$ such that every graph $G$ on $n$ vertices has at most $O(2^{(1-varepsilon)n})$ minimal connected dominating sets. For the same $varepsilon$ we also give an algorithm with running time $2^{(1-varepsilon)n}cdot{n}^{O(1)}$ to enumerate all minimal connected dominating sets in an input graph $G$.

Recommendations

• Enumeration of minimal connected dominating sets for chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• scientific article; zbMATH DE number 1052836
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• On maximum number of minimal dominating sets in graphs

Cites work

• An exact algorithm for connected red-blue dominating set
• An exact algorithm for the maximum leaf spanning tree problem
• Combinatorial bounds via measure and conquer
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Exact exponential algorithms.
• On cliques in graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Probability and random processes.
• Solving connected dominating set faster than \(2^n\)

Cited in

(6)

• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets
• scientific article; zbMATH DE number 1052836 (Why is no real title available?)
• Robust connectivity of graphs on surfaces
• Enumerating minimal defensive alliances
• Enumeration of minimal connected dominating sets for chordal graphs

This page was built for publication: Below all subsets for minimal connected dominating set

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