Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328715 | Discrete Applied Mathematics | 2005 | 12 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anne Bergeron,