๐ฎ
๐ฎ
The Ethereal
Enumerating minimal dominating sets in $K_t$-free graphs and variants
October 01, 2018 ยท The Ethereal ยท ๐ ACM Trans. Algorithms
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal