A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

DOI10.1016/J.DAM.2015.09.019zbMath1332.05108OpenAlexW1865895387MaRDI QIDQ260042

Dmitriy S. Malyshev

Publication date: 18 March 2016

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

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

zbMATH Keywords

computational complexitypolynomial-time algorithmdominating set problemhereditary class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Unnamed Item ⋮ FPT-algorithm for computing the width of a simplex given by a convex hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• 4-coloring \(H\)-free graphs when \(H\) is small
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Boundary classes of graphs for the dominating set problem
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Boundary graph classes for some maximum induced subgraph problems
• Boundary properties of the satisfiability problems
• NP-hard graph problems and boundary classes of graphs
• List coloring in the absence of two subgraphs
• On the complexity of domination number determination in monogenic classes of graphs
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs