On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
From MaRDI portal
Publication:499360
DOI10.1016/j.dam.2015.02.010zbMath1321.05184OpenAlexW2078929674MaRDI QIDQ499360
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Colouring vertices of triangle-free graphs without forests
- Domination, independent domination, and duality in strongly chordal graphs
- Dominating sets for split and bipartite graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Dominating sets in planar graphs
- Domination and total domination on asteroidal triple-free graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Clique-width for 4-vertex forbidden subgraphs
- Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs
- The Complexity of the Partial Order Dimension Problem
- Edge Dominating Sets in Graphs
- Dominating Sets in Chordal Graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Domination in Graphs Applied to Electric Power Networks
- Lower Bounds and Algorithms for Dominating Sets in Web Graphs
- A dominating-set-based routing scheme in ad hoc wireless networks
