On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
type: Item
instance of: scholarly article
title: On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
zbMATH Open document ID: 1321.05184
author: Min Chih Lin
author: Michel J. Mizrahi
published in: Discrete Applied Mathematics
publication date: 2015-09-30T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6487398
zbMATH Keywords: dominating set
zbMATH Keywords: complexity
zbMATH Keywords: algorithms
zbMATH Keywords: forbidden induced subgraphs
MaRDI profile type: Publication
full work available at URL: j.dam.2015.02.010
OpenAlex ID: W2078929674
cites work: Dominating sets for split and bipartite graphs
cites work: Q4425939
cites work: Dominating Sets in Chordal Graphs
cites work: Clique-width for 4-vertex forbidden subgraphs
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
cites work: Lower Bounds and Algorithms for Dominating Sets in Web Graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Colouring vertices of triangle-free graphs without forests
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Edge Dominating Sets in Graphs
cites work: Domination in Graphs Applied to Electric Power Networks
cites work: Q4368728
cites work: Finding and counting small induced subgraphs efficiently
cites work: Domination and total domination on asteroidal triple-free graphs
cites work: Q2934676
cites work: Dominating sets in planar graphs
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
cites work: Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
cites work: A dominating-set-based routing scheme in ad hoc wireless networks
cites work: The Complexity of the Partial Order Dimension Problem
cites work: Q4405639
DOI: 10.1016/J.DAM.2015.02.010
Recommended article: A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Recommended article: Q5009538
Recommended article: On Minrank and Forbidden Subgraphs
Recommended article: Q5884490
Recommended article: The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
Recommended article: The algorithmic complexity of minus domination in graphs
Recommended article: Algorithmic Aspect of Minus Domination on Small-Degree Graphs
Recommended article: A note on the complexity of minimum dominating set
Recommended article: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
Recommended article: On the complexity of the minimum outer-connected dominating set problem in graphs
description: scientific article; zbMATH DE number 6487398