کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950580 1440713 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Editing to a connected graph of given degrees
ترجمه فارسی عنوان
ویرایش به گراف متصل از درجه داده شده است
کلمات کلیدی
ویرایش گراف، محدودیت های درجه اتصال پیچیدگی پارامتریک،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks, given a graph G, non-negative integers d,k and a function δ:V(G)→{1,…,d}, whether it is possible to obtain a connected graph G′ from G such that the degree of v is δ(v) for every vertex v by at most k edge editing operations. As the problem is NP-complete even if δ(v)=2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d+k. For the special case δ(v)=d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 131-147
نویسندگان
,