Sorting by prefix block-interchanges

Anthony Labarre (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We initiate the study of sorting permutations using prefix block-interchanges, which exchange any prefix of a permutation with another non-intersecting interval. The goal is to transform a given permutation into the identity permutation using as few such operations as possible. We give a 2-approximation algorithm for this problem, show how to obtain improved lower and upper bounds on the corresponding distance, and determine the largest possible value for that distance.

Keywords: permutations; genome rearrangements; interconnection network; sorting; edit distance; prefix block-interchange

Domains: Data Structures and Algorithms [cs.DS]; Data Structures and Algorithms [cs.DS]

Anthony Labarre. Sorting by prefix block-interchanges. ISAAC 2020, Dec 2020, Hong-Kong, China. pp.55:1-55:15, ⟨10.4230/LIPIcs.ISAAC.2020.55⟩. ⟨hal-02926790⟩