Title: New bounds and tractable instances for the transposition distance
Authors: Labarre, Anthony # ×
Issue Date: Oct-2006
Publisher: IEEE Computer Society
Series Title: IEEE/ACM Transactions on Computational Biology and Bioinformatics vol:3 issue:4 pages:380-394
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.
ISSN: 1545-5963
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
tcbb2006.pdfMain article Published 2160KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science