Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants

DOI10.1145/3386686zbMath1484.68153arXiv1810.00789OpenAlexW3033151368MaRDI QIDQ4987460

Michał Pilipczuk, Marc Heinrich, Oscar Defrain, Marthe Bonamy, Jean-Florent Raymond

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.00789

zbMATH Keywords

forbidden induced subgraphsminimal dominating setsalgorithmic enumeration

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Locally definable vertex set properties are efficiently enumerable ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ On the dualization in distributive lattices and related problems ⋮ Translating between the representations of a ranked convex geometry

This page was built for publication: Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants