Counting Minimal Dominating Sets
Publication:2988832
DOI10.1007/978-3-319-55911-7_24zbMath1485.68188OpenAlexW2601850727MaRDI QIDQ2988832
Mamadou Moustapha Kanté, Takeaki Uno
Publication date: 19 May 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_24
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Recurrence relations and splitting formulas for the domination polynomial
- The complexity of computing the permanent
- Computational aspects of monotone dualization: a brief survey
- On the counting complexity of propositional circumscription
- Linear delay enumeration and monadic second-order logic
- Approximating the permanent of graphs with large factors
- Block interpolation: a framework for tight exponential-time counting complexity
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Complexity of generalized satisfiability counting problems
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Faster Algorithms to Enumerate Hypergraph Transversals
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Dominating Set Counting in Graph Classes
- Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- On the Enumeration of Minimal Dominating Sets and Related Notions
This page was built for publication: Counting Minimal Dominating Sets
