A decidability result for the dominating set problem

DOI10.1016/j.tcs.2010.08.027zbMath1238.05199MaRDI QIDQ410736

Vadim V. Lozin

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.027

zbMATH Keywords

computational complexity; decidability; dominating set; well-quasi-order; non-constructive proof

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Graph isomorphism for graph classes characterized by two forbidden induced subgraphs, Towards an isomorphism dichotomy for hereditary graph classes, List coloring in the absence of two subgraphs

Cites Work

• Graph minors. XX: Wagner's conjecture
• Dominating sets for split and bipartite graphs
• Domination in convex and chordal bipartite graphs
• Nonconstructive advances in polynomial-time complexity
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Line graphs and forbidden induced subgraphs
• Boundary classes of graphs for the dominating set problem
• NP-hard graph problems and boundary classes of graphs
• Domination in permutation graphs
• Nonconstructive tools for proving polynomial-time decidability
• Edge Dominating Sets in Graphs
• Subgraphs and well‐quasi‐ordering
• Ordering by Divisibility in Abstract Algebras
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item