کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435719 689930 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Obtaining split graphs by edge contraction
ترجمه فارسی عنوان
گرفتن نمودارهای تقسیم شده توسط انقباض لبه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We study the parameterized complexity of the following Split Contraction problem: Given a graph G, and an integer k as parameter, determine whether G can be modified into a split graph by contracting at most k edges. We show that Split Contraction can be solved in FPT time 2O(k2)n52O(k2)n5, but admits no polynomial kernel unless NP⊆coNP/polyNP⊆coNP/poly.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 607, Part 1, 23 November 2015, Pages 60–67
نویسندگان
, ,