A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs

DOI10.1007/978-3-662-53174-7_11zbMath1417.05215arXiv1407.2036OpenAlexW1583936026MaRDI QIDQ2827808

Mamadou Moustapha Kanté, Arnaud Mary, Vincent Limouzy, Takeaki Uno, Lhouari Nourine

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Minimal Roman dominating functions: extensions and enumeration ⋮ Invited talks ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ On the complexity of solution extension of optimization problems ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• Linear delay enumeration and monadic second-order logic
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
• Enumeration of the Monomials of a Polynomial and Related Complexity Classes
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
• On the Enumeration of Minimal Dominating Sets and Related Notions

This page was built for publication: A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs