کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418564 | 681688 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
ترجمه فارسی عنوان
در پیچیدگی حداقل مشکل سلطه محدود شده توسط زیرگراف های منع شده ممنوع از اندازه های کوچک است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
غرور مجموعه، پیچیدگی، الگوریتم ها، زیرگراف های القا شده ممنوع
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the computational complexity of the minimum dominating set problem on graphs restricted by forbidden induced subgraphs. We give some dichotomies results for the problem on graphs defined by any combination of forbidden induced subgraphs with at most four vertices, implying either an NP-Hardness proof or a polynomial time algorithm. We also extend the results by showing that dominating set problem remains NP-hard even when the graph has maximum degree three, it is planar and has no induced claw, induced diamond, induced K4K4 nor induced cycle of length 4, 5, 7, 8, 9, 10 and 11.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 53–58
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 53–58
نویسندگان
Min Chih Lin, Michel J. Mizrahi,