Sorting by short block-moves

Sorting permutations by operations such as reversals and block-moves has re ceived much interest because of its applications in the study of genome rea rrangements and in the design of interconnection networks. A short block-mo ve is an operation on a permutation that moves an element at most two posit ions away from its original position. This paper investigates the problem o f finding a minimum-length sorting sequence of short block-moves for a give n permutation. A 4/3-approximation algorithm for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorith m for this class of permutations is devised that employs graph matching tec hniques. A linear-time maximum matching algorithm for a special class of gr id graphs improves the time complexity of the algorithm for woven double-st rip permutations.