Enumeration of minimal dominating sets and variants

DOI10.1007/978-3-642-22953-4_26zbMATH Open1342.05099OpenAlexW151243703MaRDI QIDQ3088292FDOQ3088292

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (28)

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

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)