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

List coloring in the absence of two subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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