کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952497 | 1442039 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized tractability of the maximum-duo preservation string mapping problem
ترجمه فارسی عنوان
رعایت پارامترهای مشکل حداکثر دوو حفظ رشته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زیست شناسی محاسباتی، پارتیشن رشته مشترک، الگوریتم های پارامتریک، کرنل کردن،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O(k6).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 646, 20 September 2016, Pages 16-25
Journal: Theoretical Computer Science - Volume 646, 20 September 2016, Pages 16-25
نویسندگان
Stefano Beretta, Mauro Castelli, Riccardo Dondi,