Heath, Lenwood S.Vergara, John Paul C.2013-06-192013-06-191998-02-01http://hdl.handle.net/10919/19985Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in computational biology, particularly in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3-approximation algorithm for this problem is presented. Exact polynomial-time algorithms are presented for woven bitonic permutations and woven double-strip permutations. A linear-time maximum matching algorithm for a special class of grid graphs is also discovered that improves the time complexity of one of these exact algorithms.application/postscriptenIn CopyrightTechnical reportTR-98-03http://eprints.cs.vt.edu/archive/00000482/01/TR-98-03.ps