Skip to Main content Skip to Navigation
Journal articles

New bounds and tractable instances for the transposition distance

Abstract : The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few nontrivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Anthony Labarre Connect in order to contact the contributor
Submitted on : Friday, September 7, 2012 - 9:45:00 AM
Last modification on : Tuesday, October 19, 2021 - 12:55:33 PM
Long-term archiving on: : Saturday, December 8, 2012 - 3:40:07 AM


Files produced by the author(s)




Anthony Labarre. New bounds and tractable instances for the transposition distance. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2006, 3 (4), pp.380-394. ⟨10.1109/TCBB.2006.56⟩. ⟨hal-00728947⟩



Record views


Files downloads