کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952249 | 1442024 | 2017 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph editing to a given degree sequence
ترجمه فارسی عنوان
ویرایش گراف به دنباله درجه مشخص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، ویرایش گراف، توالی درجه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence Ï by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W[1]-hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2O(k(Îâ+k)2)n2logâ¡n for n-vertex graphs, where Îâ=maxâ¡Ï, i.e., the problem is FPT when parameterized by k+Îâ. We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k+Îâ if only edge additions are allowed, and there is no polynomial kernel unless NPâco-NP/poly for all other combinations of the allowed editing operations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 665, 22 February 2017, Pages 1-12
Journal: Theoretical Computer Science - Volume 665, 22 February 2017, Pages 1-12
نویسندگان
Petr A. Golovach, George B. Mertzios,