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

چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 411, Issues 44–46, 25 October 2010, Pages 4023-4027