کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435719 | 689930 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Obtaining split graphs by edge contraction
ترجمه فارسی عنوان
گرفتن نمودارهای تقسیم شده توسط انقباض لبه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 607, Part 1, 23 November 2015, Pages 60–67
نویسندگان
Chengwei Guo, Leizhen Cai,