Sorting by short swaps.
A short swap is an operation on a permutation that switches two elements that have at most one element between them. This paper investigates the problem of finding a minimum-length sorting sequence of short swaps for a given permutation. A polynomial-time 2-approximation algorithm for this problem is presented, and bounds for the short-swap diameter (the length of the longest minimum sorting sequence among all permutations of a given length) are also obtained.
Heath
Lenwood S
LS
Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061-0106, USA. heath@vt.edu
Vergara
John Paul C
JP
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D016678:Genome; D008957:Models, Genetic; D015203:Reproducibility of Results