کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428479 | 686775 | 2016 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
ترجمه فارسی عنوان
یک الگوریتم FPT برای اصلاح یک گراف از عرض درخت محدود شده برای کاهش اندازه مجموعه غالب آن با استفاده از حداقل اصلاح ☆
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تسلط مجموعه؛ ردیابی پارامتر پارامتر تجزیه درخت؛ پیچیدگی محاسباتی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we study the problem of modifying a graph such that the resulting graph has a dominating set of size at most k. Solving this problem determines the minimum number of edges to be added to a given graph such that at most k vertices can dominate all vertices. We show that this problem is NP-hard, and therefore, has no polynomial-time algorithm (unless P=NPP=NP). Also, we show that the problem is FPT parameterized by the treewidth of the input graph. Furthermore, we show that the problem parameterized by k is W[2]-hard and belongs to W[P].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 9, September 2016, Pages 590–594
Journal: Information Processing Letters - Volume 116, Issue 9, September 2016, Pages 590–594
نویسندگان
Mehdy Roayaei, Mohammadreza Razzazi,