Enumerating Minimal Dominating Sets in Triangle-Free Graphs

DOI10.4230/LIPIcs.STACS.2019.16OpenAlexW2963944565MaRDI QIDQ5090462

Jean-Florent Raymond, Marthe Bonamy, Oscar Defrain, Marc Heinrich

Publication date: 18 July 2022

Full work available at URL: https://hal.archives-ouvertes.fr/hal-02181721

zbMATH Keywords

split graphstriangle-free graphsenumeration algorithmsminimal dominating setoutput-polynomial algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Minimal Roman dominating functions: extensions and enumeration ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Cites Work

• Unnamed Item
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Enumerating maximal independent sets with applications to graph colouring.
• Enumerating minimal dominating sets in chordal bipartite graphs
• Computational aspects of monotone dualization: a brief survey
• Linear delay enumeration and monadic second-order logic
• Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
• Analysis and enumeration. Algorithms for biological graphs
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• Enumeration of Minimal Dominating Sets and Variants
• Enumeration of the Monomials of a Polynomial and Related Complexity Classes
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
• Enumeration of the Elementary Circuits of a Directed Graph
• On the Enumeration of Minimal Dominating Sets and Related Notions
• Parameterized and Exact Computation
• An efficient search algorithm to find the elementary circuits of a graph
• The Enumeration of Maximal Cliques of Large Graphs

This page was built for publication: Enumerating Minimal Dominating Sets in Triangle-Free Graphs