Below all subsets for minimal connected dominating set

DOI10.1137/17M1138753zbMATH Open1396.05052arXiv1611.00840OpenAlexW2548944478WikidataQ129189621 ScholiaQ129189621MaRDI QIDQ4683902FDOQ4683902

Saket Saurabh, Daniel Lokshtanov, Michał Pilipczuk

Publication date: 26 September 2018

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

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$.

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

Recommendations

• Enumeration of minimal connected dominating sets for chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Publication:4351076
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• On maximum number of minimal dominating sets in graphs

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Enumeration of minimal connected dominating sets for chordal graphs
• Robust Connectivity of Graphs on Surfaces

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)