Sorting by prefix block-interchanges

DOI10.1016/J.TCS.2023.113857OpenAlexW3081674494MaRDI QIDQ6038693FDOQ6038693

Authors Anthony Labarre

Publication date 2 May 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.13640

zbMATH Keywords

permutationsdistanceinterconnection networksortinggenome rearrangementsprefix block-interchange

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 7765413
• Sorting permutations by block-interchanges
• Sorting by prefix reversals and prefix transpositions
• Sorting by bounded block-moves
• Sorting by short block-moves
• Sorting permutations by prefix and suffix versions of reversals and transpositions
• Sorting by Transpositions
• Sorting by exchanging
• APPROXIMATE BLOCK SORTING

Cites work

• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Combinatorics of genome rearrangements.
• Lower bounding edit distances between permutations
• On sorting unsigned permutations by double-cut-and-joins
• On the parameterized complexity of short computation and factorization
• Polynomial-time sortable stacks of burnt pancakes
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The complexity of finding minimum-length generator sequences
• Transforming cabbage into turnip
• \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges

Cited in

(3)

• Sorting genomes by prefix double-cut-and-joins
• Sorting genomes by prefix double-cut-and-joins
• scientific article; zbMATH DE number 7765413 (Why is no real title available?)

This page was built for publication: Sorting by prefix block-interchanges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038693)