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)

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

• Title not available (Why is that?)
• 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)

• 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)