کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952249 1442024 2017 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph editing to a given degree sequence
ترجمه فارسی عنوان
ویرایش گراف به دنباله درجه مشخص
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,