کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10333037 688187 2005 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sorting signed permutations by reversals, revisited
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Sorting signed permutations by reversals, revisited
چکیده انگلیسی
Finally, we present the first efficient parallel algorithm for SBR. We obtain this result by developing a fast implementation of the recent algorithm of Bergeron (Proceedings of CPM, 2001, pp. 106-117) for sorting signed permutations by reversals that is parallelizable. Our implementation runs in O(n2logn) time on a regular RAM, and in O(nlogn) time on a PRAM using n processors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 70, Issue 3, May 2005, Pages 321-341
نویسندگان
, ,