Enumerating minimal dominating sets in $K_t$-free graphs and variants

October 01, 2018 ยท The Ethereal ยท ๐Ÿ› ACM Trans. Algorithms

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Marthe Bonamy, Oscar Defrain, Marc Heinrich, Jean-Florent Raymond, Michaล‚ Pilipczuk arXiv ID 1810.00789 Category cs.DM: Discrete Mathematics Cross-listed cs.DS Citations 15 Venue ACM Trans. Algorithms Last Checked 2 months ago
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 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รฉ et al. about enumeration in bipartite graphs.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Discrete Mathematics