کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434042 | 689673 | 2015 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Editing to a Graph of Given Degrees
ترجمه فارسی عنوان
ویرایش به یک نمودار از مدارک داده شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، ویرایش گراف، نمودارهای درجه داده شده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the Editing to a Graph of Given Degrees problem that asks for a graph G , non-negative integers d,kd,k and a function δ:V(G)→{1,…,d}δ:V(G)→{1,…,d}, whether it is possible to obtain a graph G′G′ from G such that the degree of v is δ(v)δ(v) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for Editing to a Graph of Given Degrees parameterized by d+kd+k. We complement this result by showing that the problem has no polynomial kernel unless NP⊆coNP/polyNP⊆coNP/poly.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 591, 2 August 2015, Pages 72–84
Journal: Theoretical Computer Science - Volume 591, 2 August 2015, Pages 72–84
نویسندگان
Petr A. Golovach,