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

DOI10.1016/J.DAM.2015.02.010zbMATH Open1321.05184OpenAlexW2078929674MaRDI QIDQ499360FDOQ499360

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

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
• scientific article; zbMATH DE number 7667277
• 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

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)

Cites Work

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

Cited In (3)

• Graphs as \(r\)-minoes
• Preface
• Complexity of computing of the domination number in hereditary classes of graphs.

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)