Minimal dominating sets in interval graphs and trees

DOI10.1016/J.DAM.2016.01.038MaRDI QIDQ344851zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Yngve Villanger

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.01.038

zbMATH Keywords

enumerationgraph classesminimal dominating sets

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• On the number of minimal dominating sets on some graph classes
• The maximum number of minimal dominating sets in a tree
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• Trees having many minimal dominating sets

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Combinatorial bounds via measure and conquer
• Enumerating maximal independent sets with applications to graph colouring.
• Enumerating minimal subset feedback vertex sets
• Enumeration of minimal dominating sets and variants
• Exact exponential algorithms.
• Feedback vertex sets in tournaments
• Finding induced subgraphs via minimal triangulations
• Graph Classes: A Survey
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On cliques in graphs
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• On the enumeration of minimal dominating sets and related notions
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
• On the number of minimal dominating sets on some graph classes
• Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Subset feedback vertex sets in chordal graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Trees having many minimal dominating sets

Cited in

(12)

• On the complexity of solution extension of optimization problems
• Majorization and the minimum number of dominating sets
• Minimal Double Dominating Sets in Trees
• On the number of minimal dominating sets on some graph classes
• Domination cover number of graphs
• Minimum-cost b-edge dominating sets on trees
• Reconfiguring minimum dominating sets: the -graph of a tree
• Enumeration of minimal connected dominating sets for chordal graphs
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• Invited talks
• scientific article; zbMATH DE number 7528053 (Why is no real title available?)
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs

This page was built for publication: Minimal dominating sets in interval graphs and trees

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