کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
417885 | 681587 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
ترجمه فارسی عنوان
دایره ای برای مسئله مجموعه غالب برای کلاس های تعریف شده توسط زیرگراف های ناشی از کوچک ممنوع
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
غلبه بر مشکل مجموعه، کلاس ارثی، پیچیدگی محاسباتی، الگوریتم زمان چندجملهای
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 203, 20 April 2016, Pages 117–126
Journal: Discrete Applied Mathematics - Volume 203, 20 April 2016, Pages 117–126
نویسندگان
D.S. Malyshev,