{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T11:32:40Z","timestamp":1789990360680,"version":"4.0.1"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["UMO-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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 $\\epsilon &gt; 10^{-50}$ such that every graph $G$ on $n$ vertices has at most $\\mathcal{O}(2^{(1-\\epsilon)n})$ minimal connected dominating sets. For the same $\\epsilon$ we also give an algorithm with running time $2^{(1-\\epsilon)n}\\cdot n^{\\mathcal{O}(1)}$ to enumerate all minimal connected dominating sets in an input graph $G$.<\/jats:p>","DOI":"10.1137\/17m1138753","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T11:58:53Z","timestamp":1537876733000},"page":"2332-2345","source":"Crossref","is-referenced-by-count":5,"title":["Below All Subsets for Minimal Connected Dominating Set"],"prefix":"10.1137","volume":"32","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.03.006"},{"key":"atypb2","unstructured":"H. L. Bodlaender, E. Boros, P. Heggernes, and D. Kratsch,\n                      Open problems of the Lorentz workshop \u201cEnumeration Algorithms using Structure\n                      ,\u201d Utrecht University Technical Report UU-CS-2015-016, 2015,http:\/\/www.cs.uu.nl\/research\/techreps\/repo\/CS-2015\/2015-016.pdf."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.011"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9145-z"},{"key":"atypb6","first-page":"5","author":"Fomin F. V.","year":"2008","journal-title":"ACM Trans. Algorithms"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch,\n                      Exact Exponential Algorithms\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, New York, 2010.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.03.026"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. Grimmett and D. Stirzaker,\n                      Probability and Random Processes\n                      , Oxford University Press, Oxford, UK, 2001.","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1138753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:42Z","timestamp":1787320782000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1138753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1138753"],"URL":"https:\/\/doi.org\/10.1137\/17m1138753","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}