A decidability result for the dominating set problem

DOI10.1016/j.tcs.2010.08.027zbMath1238.05199OpenAlexW2147525506MaRDI 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 complexitydecidabilitydominating setwell-quasi-ordernon-constructive proof

Mathematics Subject Classification ID

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)

Related Items (3)

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

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

This page was built for publication: A decidability result for the dominating set problem