Sorting by prefix block-interchanges

DOI10.1016/J.TCS.2023.113857arXiv2008.13640OpenAlexW3081674494MaRDI QIDQ6038693FDOQ6038693

Authors: Anthony Labarre 

Publication date: 2 May 2023

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

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.

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

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

zbMATH Keywords

permutationsdistanceinterconnection networksortinggenome rearrangementsprefix block-interchange

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Sorting genomes by prefix double-cut-and-joins
• Sorting genomes by prefix double-cut-and-joins

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)