Below all subsets for Minimal Connected Dominating Set

November 02, 2016 Β· Declared Dead Β· πŸ› SIAM Journal on Discrete Mathematics

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Daniel Lokshtanov, MichaΕ‚ Pilipczuk, Saket Saurabh arXiv ID 1611.00840 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 8 Venue SIAM Journal on Discrete Mathematics Last Checked 4 months ago
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$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted