کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
417885 681587 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
ترجمه فارسی عنوان
دایره ای برای مسئله مجموعه غالب برای کلاس های تعریف شده توسط زیرگراف های ناشی از کوچک ممنوع
کلمات کلیدی
غلبه بر مشکل مجموعه، کلاس ارثی، پیچیدگی محاسباتی، الگوریتم زمان چندجملهای
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
,