Enumeration of minimal dominating sets and variants

DOI10.1007/978-3-642-22953-4_26MaRDI QIDQ3088292zbMATH OpenOpenAlexFDO

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

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

Enumeration in graph theory (05C30) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On the enumeration of minimal dominating sets and related notions
• 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
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal bipartite graphs

Cites work

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

Cited in

(30)

• Structural parameterizations of dominating set variants
• Enumeration of maximal irredundant sets for claw-free graphs
• The k-hop connected dominating set problem: approximation and hardness
• Locally definable vertex set properties are efficiently enumerable
• Efficient enumeration of dominating sets for sparse graphs
• Subset feedback vertex sets in chordal 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
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Enumerating Minimal Tropical Connected Sets
• The k-hop connected dominating set problem: hardness and polyhedra
• Minimal dominating sets in interval graphs and trees
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• scientific article; zbMATH DE number 1522332 (Why is no real title available?)
• On the number of minimal dominating sets on some graph classes
• On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• Efficient enumeration of dominating sets for sparse graphs
• On the enumeration of minimal dominating sets and related notions
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Minimal enumerations of subsets of a finite set and the middle level problem
• Minimal Roman dominating functions: extensions and enumeration
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraints
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Enumerating minimal connected dominating sets
• Roman hitting functions

This page was built for publication: Enumeration of minimal dominating sets and variants

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