Enumeration of Minimal Dominating Sets and Variants

DOI10.1007/978-3-642-22953-4_26zbMath1342.05099OpenAlexW151243703MaRDI QIDQ3088292

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

Publication date: 19 August 2011

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22953-4_26

Mathematics Subject Classification ID

Hypergraphs (05C65) 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

Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration, Enumeration of maximal irredundant sets for claw-free graphs, The \(k\)-hop connected dominating set problem: hardness and polyhedra, Minimal dominating sets in interval graphs and trees, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, The \(k\)-hop connected dominating set problem: approximation and hardness, Subset feedback vertex sets in chordal graphs, On the number of minimal dominating sets on some graph classes, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Efficient enumeration of dominating sets for sparse graphs, Unnamed Item, Enumerating Minimal Dominating Sets in Triangle-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Computational aspects of monotone dualization: a brief survey
• Total domination of graphs and small transversals of hypergraphs
• Linear delay enumeration and monadic second-order logic
• Enumeration aspects of maximal cliques and bicliques
• Graph minors. V. Excluding a planar graph
• On generating all maximal independent sets
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Hypertree width and related hypergraph invariants
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Graph Classes: A Survey
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions
• Combinatorial bounds via measure and conquer
• On the Enumeration of Minimal Dominating Sets and Related Notions
• A dominating-set-based routing scheme in ad hoc wireless networks