VTechWorks staff will be away for the Memorial Day holiday on Monday, May 27, and will not be replying to requests at that time. Thank you for your patience.
Sorting by Short Block-Moves
Heath, Lenwood S.
Vergara, John Paul C.
MetadataShow full item record
Sorting 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.