Minimal dominating sets in interval graphs and trees
From MaRDI portal
Publication:344851
DOI10.1016/j.dam.2016.01.038zbMath1350.05121OpenAlexW2283788147MaRDI QIDQ344851
Dieter Kratsch, Yngve Villanger, Pinar Heggernes, Petr A. Golovach, Mamadou Moustapha Kanté
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
Trees (05C05) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Enumeration of minimal connected dominating sets for chordal graphs ⋮ Invited talks ⋮ Domination cover number of graphs ⋮ Unnamed Item ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs ⋮ On the complexity of solution extension of optimization problems
Cites Work
- Unnamed Item
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Enumerating minimal subset feedback vertex sets
- On the number of minimal dominating sets on some graph classes
- Exact exponential algorithms.
- Enumerating maximal independent sets with applications to graph colouring.
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Algorithmic graph theory and perfect graphs
- Trees having many minimal dominating sets
- Subset feedback vertex sets in chordal graphs
- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
- Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
- Enumeration of Minimal Dominating Sets and Variants
- Finding Induced Subgraphs via Minimal Triangulations
- Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- Graph Classes: A Survey
- The Number of Maximal Independent Sets in Triangle-Free Graphs
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Feedback Vertex Sets in Tournaments
- On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
- Combinatorial bounds via measure and conquer
- On the Enumeration of Minimal Dominating Sets and Related Notions
- An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets
- On cliques in graphs
This page was built for publication: Minimal dominating sets in interval graphs and trees