Merging and sorting by strip moves

We consider two problems related to the well-studied sorting by transpositions problem: (1) Given a permutation, sort it by moving a minimum number of strips, where a strip is a maximal substring of the permutation which is also a substring of the identity permutation, and (2) Given a set of increasing sequences of distinct elements, merge them into one increasing sequence with a minimum number of strip moves. We show that the merging by strip moves problem has a polynomial time algorithm. Using this, we give a 2-approximation algorithm for the sorting by strip moves problem. We also observe that the sorting by strip moves problem, as well as the sorting by transpositions problem, are fixed-parameter-tractable. © Springer-Verlag Berlin Heidelberg 2003.