Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants
| Autor: | Michał Pilipczuk, Marc Heinrich, Marthe Bonamy, Jean-Florent Raymond, Oscar Defrain |
|---|---|
| Přispěvatelé: | Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), MIMUW - Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, University of Warsaw (UW), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Computer science Open problem [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Induced subgraph G.2.1 G.2.2 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Combinatorics Mathematics (miscellaneous) Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Enumeration Data Structures and Algorithms (cs.DS) 68R05 68R10 05C30 05C69 05C85 Mathematics::Combinatorics 16. Peace & justice Graph 010201 computation theory & mathematics Bipartite graph 020201 artificial intelligence & image processing F.0 Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | ACM Transactions on Algorithms ACM Transactions on Algorithms, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩ ACM Transactions on Algorithms, Association for Computing Machinery, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩ |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/3386686 |
| Popis: | It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for $K_t$-free graphs and variants. This answers a question of Kant\'e et al. about enumeration in bipartite graphs. Comment: 26 pages. A preliminary version of this article appeared in the proceedings of the 36th Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|