کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10328715 684870 2005 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A very elementary presentation of the Hannenhalli-Pevzner theory
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A very elementary presentation of the Hannenhalli-Pevzner theory
چکیده انگلیسی
In 1995, Hannenhalli and Pevzner gave a first polynomial solution to the problem of finding the minimum number of reversals needed to sort a signed permutation. Their solution, as well as subsequent ones, relies on many intermediary constructions, such as simulations with permutations on 2n elements, and manipulation of various graphs. Here we give the first completely elementary treatment of this problem. We characterize safe reversals and hurdles working directly on the original signed permutation. Moreover, our presentation leads to polynomial algorithms that can be efficiently implemented using bit-wise operations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 2, 1 March 2005, Pages 134-145
نویسندگان
,