کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430571 | 688045 | 2013 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The constrained shortest common supersequence problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The constrained shortest common supersequence problem The constrained shortest common supersequence problem](/preview/png/430571.png)
چکیده انگلیسی
Shortest common supersequence and longest common subsequence are two widely used measures to compare sequences in different fields, from AI planning to Bioinformatics. Inspired by recently proposed variants of these two measures, we introduce a new version of the shortest common supersequence problem, where the solution is required to satisfy a given constraint on the number of occurrences of each symbol. First, we investigate the computational and approximation complexity of the problem, then we give a 32-approximation algorithm. Finally, we investigate the parameterized complexity of the problem, and we present a fixed-parameter algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 21, July 2013, Pages 11–17
Journal: Journal of Discrete Algorithms - Volume 21, July 2013, Pages 11–17
نویسندگان
Riccardo Dondi,