A decidability result for the dominating set problem

作者：Lozin Vadim V^*

来源：Theoretical Computer Science, 2010, 411(44-46): 4023-4027.

DOI：10.1016/j.tcs.2010.08.027

• Dominating set
• Computational complexity
• Decidability
• Well-quasi-order
• Non-constructive proof

We study the following question: given a finite collection of graphs G(1), ..., G(k), is the dominating set problem polynomial-time solvable in the class of (G(1), ..., G(k))-free graphs? In this paper, we prove the existence of an efficient algorithm that answers this question for k = 2.

• 出版日期2010-10-25