{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T02:39:59Z","timestamp":1784774399273,"version":"3.55.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}]},{"name":"ANR","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["677651"],"award-info":[{"award-number":["677651"]}]},{"name":"ERC consolidator","award":["DISTRUCT-648527"],"award-info":[{"award-number":["DISTRUCT-648527"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>\n            It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for\n            <jats:italic>\n              K\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            -free graphs and for several related graph classes. This answers a question of Kant\u00e9 et al. about enumeration in bipartite graphs.\n          <\/jats:p>","DOI":"10.1145\/3386686","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants"],"prefix":"10.1145","volume":"16","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[{"name":"CNRS, LaBRI, Universit\u00e9 de Bordeaux, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9203-1530","authenticated-orcid":false,"given":"Oscar","family":"Defrain","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Heinrich","sequence":"additional","affiliation":[{"name":"LIRIS, Universit\u00e9 Claude-Bernard, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4646-7602","authenticated-orcid":false,"given":"Jean-Florent","family":"Raymond","sequence":"additional","affiliation":[{"name":"CNRS, LIMOS, Universit\u00e9 Clermont Auvergne, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00014a001"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Bonamy Marthe","year":"2019","unstructured":"Marthe Bonamy , Oscar Defrain , Marc Heinrich , and Jean-Florent Raymond . 2019 . Enumerating minimal dominating sets in triangle-free graphs . In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. 2019. Enumerating minimal dominating sets in triangle-free graphs. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.021"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.026"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45757-7_53"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240639X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.04.017"},{"key":"e_1_2_1_10_1","first-page":"63","article-title":"Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421)","volume":"8","author":"Fernau Henning","year":"2019","unstructured":"Henning Fernau , Petr A. Golovach , and Marie-France Sagot . 2019 . Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421) . Dagstuhl Rep. 8 , 10 (2019), 63 -- 86 . DOI:https:\/\/doi.org\/10.4230\/DagRep.8.10.63 10.4230\/DagRep.8.10.63 Henning Fernau, Petr A. Golovach, and Marie-France Sagot. 2019. Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Rep. 8, 10 (2019), 63--86. DOI:https:\/\/doi.org\/10.4230\/DagRep.8.10.63","journal-title":"Dagstuhl Rep."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435384"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0062"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00049-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0289-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.12.010"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9875-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.017"},{"key":"e_1_2_1_18_1","volume-title":"Grochow and Manolis Kellis","author":"Joshua","year":"2007","unstructured":"Joshua A. Grochow and Manolis Kellis . 2007 . Network motif discovery using subgraph enumeration and symmetry-breaking. In Proceedings of the Annual International Conference on Research in Computational Molecular Biology. Springer , 92--106. Joshua A. Grochow and Manolis Kellis. 2007. Network motif discovery using subgraph enumeration and symmetry-breaking. In Proceedings of the Annual International Conference on Research in Computational Molecular Biology. Springer, 92--106."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22953-4_26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35261-4_32"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/120862612"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_32"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 138--153","author":"Kant\u00e9 Mamadou M.","year":"2015","unstructured":"Mamadou M. Kant\u00e9 , Vincent Limouzy , Arnaud Mary , Lhouari Nourine , and Takeaki Uno . 2015 . A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs . In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 138--153 . Mamadou M. Kant\u00e9, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. 2015. A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 138--153."},{"key":"e_1_2_1_25_1","volume-title":"Kant\u00e9 and Lhouari Nourine","author":"Mamadou","year":"2016","unstructured":"Mamadou M. Kant\u00e9 and Lhouari Nourine . 2016 . Minimal dominating set enumeration. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer US , Boston, MA, 1287--1291. DOI:https:\/\/doi.org\/10.1007\/978-3-642-27848-8_721-1 10.1007\/978-3-642-27848-8_721-1 Mamadou M. Kant\u00e9 and Lhouari Nourine. 2016. Minimal dominating set enumeration. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer US, Boston, MA, 1287--1291. DOI:https:\/\/doi.org\/10.1007\/978-3-642-27848-8_721-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.85.0537"},{"key":"e_1_2_1_27_1","volume-title":"Analysis and Enumeration: Algorithms for Biological Graphs","author":"Marino Andrea","unstructured":"Andrea Marino . 2015. Analysis and Enumeration: Algorithms for Biological Graphs . Vol. 6 . Springer . Andrea Marino. 2015. Analysis and Enumeration: Algorithms for Biological Graphs. Vol. 6. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1959.5222697"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","author":"Raymond Jean-Florent","year":"2019","unstructured":"Jean-Florent Raymond . 2019 . minimal_dominating_sets, an Implementation of Bonamy et al.\u2019s Algorithm for Enumerating Minimal Dominating Sets in -free Graphs . Retrieved February 25, 2020 https:\/\/git.sagemath.org\/sage.git\/commit?id=906cf147fe64ceed73d30fabf61155f65393bd67. Jean-Florent Raymond. 2019. minimal_dominating_sets, an Implementation of Bonamy et al.\u2019s Algorithm for Enumerating Minimal Dominating Sets in -free Graphs. Retrieved February 25, 2020 https:\/\/git.sagemath.org\/sage.git\/commit?id=906cf147fe64ceed73d30fabf61155f65393bd67."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.3.237"},{"key":"e_1_2_1_31_1","volume-title":"Enumeration complexity. Bull. EATCS 1, 129","author":"Strozecki Yann","year":"2019","unstructured":"Yann Strozecki . 2019. Enumeration complexity. Bull. EATCS 1, 129 ( 2019 ). Yann Strozecki. 2019. Enumeration complexity. Bull. EATCS 1, 129 (2019)."},{"key":"e_1_2_1_32_1","volume-title":"Efficient enumeration of solutions produced by closure operations. Discr. Math. Theor. Comput. Sci. 21, 3","author":"Strozecki Yann","year":"2019","unstructured":"Yann Strozecki and Arnaud Mary . 2019. Efficient enumeration of solutions produced by closure operations. Discr. Math. Theor. Comput. Sci. 21, 3 ( 2019 ). Yann Strozecki and Arnaud Mary. 2019. Efficient enumeration of solutions produced by closure operations. Discr. Math. Theor. Comput. Sci. 21, 3 (2019)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202017"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/362814.362819"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_2_1_36_1","volume-title":"Enumeration of enumeration algorithms. arxiv:1605.05102","author":"Wasa Kunihiro","year":"2016","unstructured":"Kunihiro Wasa . 2016. Enumeration of enumeration algorithms. arxiv:1605.05102 ( 2016 ). Kunihiro Wasa. 2016. Enumeration of enumeration algorithms. arxiv:1605.05102 (2016)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386686","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386686","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:19Z","timestamp":1750199899000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386686"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3386686"],"URL":"https:\/\/doi.org\/10.1145\/3386686","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}