Skip to Main content Skip to Navigation
Journal articles

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants

Abstract : 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 K t -free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.
Complete list of metadata

https://hal.uca.fr/hal-03448793
Contributor : Jean-Florent Raymond Connect in order to contact the contributor
Submitted on : Thursday, November 25, 2021 - 1:12:43 PM
Last modification on : Friday, November 26, 2021 - 10:22:14 AM

Links full text

Identifiers

Citation

Marthe Bonamy, Oscar Defrain, Marc Heinrich, Michał Pilipczuk, Jean-Florent Raymond. Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants. ACM Transactions on Algorithms, Association for Computing Machinery, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩. ⟨hal-03448793⟩

Share

Metrics

Les métriques sont temporairement indisponibles