On the Enumeration of Minimal Dominating Sets and Related Notions
From MaRDI portal
Publication:5246092
DOI10.1137/120862612zbMath1310.05119arXiv1407.2053OpenAlexW2963385664MaRDI QIDQ5246092
Lhouari Nourine, Vincent Limouzy, Arnaud Mary, Mamadou Moustapha Kanté
Publication date: 17 April 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.2053
hypergraph dualizationtransversal problemconnected dominating set enumerationminimal dominating set enumerationoutput polynomial time algorithmtotal dominating set enumeration
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
Enumerating minimal connected dominating sets in graphs of bounded chordality, Enumeration of Maximal Irredundant Sets for Claw-Free Graphs, Enumeration of maximal irredundant sets for claw-free graphs, Proximity Search for Maximal Subgraph Enumeration, Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs, Extended dualization: application to maximal pattern mining, Completion and decomposition of hypergraphs into dominating sets of graphs, Minimal dominating sets in interval graphs and trees, Enumeration of minimal connected dominating sets for chordal graphs, Minimal Roman dominating functions: extensions and enumeration, Uniform clutters and dominating sets of graphs, Enumerating minimal dominating sets in chordal bipartite graphs, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, Invited talks, The many facets of upper domination, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Counting minimal transversals of \(\beta\)-acyclic hypergraphs, Counting Minimal Dominating Sets, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Enumerating Minimal Transversals of Hypergraphs without Small Holes, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Locally definable vertex set properties are efficiently enumerable, Efficient enumeration of dominating sets for sparse graphs, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph, A complexity theory for hard enumeration problems, Unnamed Item, On the dualization in distributive lattices and related problems, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Enumerating minimal dominating sets in chordal graphs, Enumeration of Minimal Dominating Sets and Variants, Upper Domination: Complexity and Approximation, Randomized generation of error control codes with automata and transducers, Linear separation of connected dominating sets in graphs, Enumerating Minimal Dominating Sets in Triangle-Free Graphs, A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs, Extension and its price for the connected vertex cover problem, Elimination properties for minimal dominating sets of graphs, Connected domination game, Enumeration of maximal common subsequences between two strings
