Counting minimal dominating sets

DOI10.1007/978-3-319-55911-7_24MaRDI QIDQ2988832zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the enumeration of minimal dominating sets and related notions
• Efficient enumeration of dominating sets for sparse graphs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants

Cites work

• Approximating the permanent of graphs with large factors
• Complexity of generalized satisfiability counting problems
• Computational aspects of monotone dualization: a brief survey
• Dominating Set Counting in Graph Classes
• Faster Algorithms to Enumerate Hypergraph Transversals
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Linear delay enumeration and monadic second-order logic
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the counting complexity of propositional circumscription
• On the enumeration of minimal dominating sets and related notions
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Recurrence relations and splitting formulas for the domination polynomial
• The complexity of computing the permanent
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The complexity of counting in sparse, regular, and planar graphs

Cited in

(17)

• Counting minimal transversals of -acyclic hypergraphs
• Calculating the minimal number of homogeneous objects to represent a plurality in a heterogeneous system of objects
• Efficient enumeration of dominating sets for sparse graphs
• Counting dominating sets and related structures in graphs
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• Maximum number of minimum dominating and minimum total dominating sets
• Counting Minimum Weighted Dominating Sets
• On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• Efficient enumeration of dominating sets for sparse graphs
• Counting dominating sets in generalized series-parallel graphs
• On the enumeration of minimal dominating sets and related notions
• Finding and Counting MSTD Sets
• Enumerating minimal defensive alliances
• Enumerating minimal dominating sets in chordal bipartite graphs

This page was built for publication: Counting minimal dominating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988832)