2026-08-07T10:23:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13399 2024-03-06T10:51:53Z ddc:004 open_access

Sorting by Prefix Block-Interchanges Labarre, Anthony permutations genome rearrangements interconnection network sorting edit distance prefix block-interchange 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anthony Labarre 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.55 urn:nbn:de:0030-drops-133991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.55 eng https://creativecommons.org/licenses/by/3.0/legalcode