A very elementary presentation of the Hannenhalli–Pevzner theory

AbstractIn 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