title: Sorting by short swaps.
abstract: 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.
authors: Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061-0106, USA. heath@vt.edu
authors: Lenwood S
authors: LS
authors: Heath
authors: John Paul C
authors: JP
authors: Vergara
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D016678:Genome; D008957:Models, Genetic; D015203:Reproducibility of Results