کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420479 | 683945 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the approximability of the Simplified Partial Digest Problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we analyse the computational complexity of an optimization version of the Simplified Partial Digest Problem (SPDP), which is a mathematical model for DNA mapping based on the results of a simplified partial digest experiment. We prove that recognizing 46.16% of the elements of the DNA map in the error-free simplified partial digest experiment is NP-hard in the strong sense. This implies that the problem of maximizing the number of correct elements of the DNA map in the error-free simplified partial digest experiment is pseudopolynomially non-approximable with the approximation ratio ρ=136.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3586–3592
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3586–3592
نویسندگان
Jacek Blazewicz, Edmund K. Burke, Marta Kasprzak, Alexandr Kovalev, Mikhail Y. Kovalyov,