Sorting Signed Permutations by Reversals in Nearly-Linear Time

Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya

Given a signed permutation on $n$ elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomic…