Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants - Archive ouverte HAL Access content directly
Journal Articles ACM Transactions on Algorithms Year : 2020

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants

, , (1) , (2) , (3)
1
2
3
Marthe Bonamy
Oscar Defrain
Marc Heinrich

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.

Dates and versions

hal-03448793 , version 1 (25-11-2021)

Identifiers

Cite

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, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩. ⟨hal-03448793⟩
16 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More