کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437714 690176 2010 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A decidability result for the dominating set problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A decidability result for the dominating set problem
چکیده انگلیسی

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

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issues 44–46, 25 October 2010, Pages 4023-4027