On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size

DOI10.1016/J.DAM.2015.02.010MaRDI QIDQ499360zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Michel J. Mizrahi

Publication date 30 September 2015

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

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

zbMATH Keywords

algorithmscomplexitydominating setforbidden induced subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs
• The complexity of some graph problems with bounded minors of their constraint matrices
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• The algorithmic complexity of minus domination in graphs
• Algorithmic aspect of minus domination on small-degree graphs
• A note on the complexity of minimum dominating set
• Minimum dominating set approximation in graphs of bounded arboricity
• On the complexity of the minimum outer-connected dominating set problem in graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1933051 (Why is no real title available?)
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• A dominating-set-based routing scheme in ad hoc wireless networks
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Clique-width for 4-vertex forbidden subgraphs
• Colouring vertices of triangle-free graphs without forests
• Dominating Sets in Chordal Graphs
• Dominating sets for split and bipartite graphs
• Dominating sets in planar graphs
• Domination and total domination on asteroidal triple-free graphs
• Domination in Graphs Applied to Electric Power Networks
• Domination, independent domination, and duality in strongly chordal graphs
• Edge Dominating Sets in Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Finding and counting small induced subgraphs efficiently
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Maximum independent sets in graphs of low degree
• The Complexity of the Partial Order Dimension Problem
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Cited in

(5)

• Complexity of computing of the domination number in hereditary classes of graphs.
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Graphs as \(r\)-minoes
• Preface

This page was built for publication: On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size

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