A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation

DOI10.1016/J.IPL.2016.06.006zbMATH Open1362.05007arXiv1402.4867OpenAlexW2474442016MaRDI QIDQ2630342FDOQ2630342

Authors: Anke van Zuylen, James Bieron, Frans Schalekamp, Gexin Yu 

Publication date: 27 July 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We consider the problem of upper bounding the number of circular transpositions needed to sort a permutation. It is well known that any permutation can be sorted using at most $n(n-1)/2$ adjacent transpositions. We show that, if we allow all adjacent transpositions, as well as the transposition that interchanges the element in position 1 with the element in the last position, then the number of transpositions needed is at most $n^2/4$. This answers an open question posed by Feng, Chitturi and Sudborough (2010).

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

Recommendations

• Improved upper bound for sorting permutations by prefix transpositions
• Upper bounds for sorting permutations with a transposition tree
• Tighter upper bound for sorting permutations with prefix transpositions
• A new upper bound for sorting permutations with prefix transpositions
• Lower bounding edit distances between permutations

zbMATH Keywords

permutationsCayley graphsdiametersortingcombinatorial problems

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A group-theoretic model for symmetric interconnection networks
• Title not available (Why is that?)
• Combinatorics of genome rearrangements.
• Title not available (Why is that?)
• Sorting with fixed-length reversals
• The complexity of finding minimum-length generator sequences
• Circular permutations and genome shuffling

Cited In (4)

• Upper bounds for sorting permutations with a transposition tree
• On the diameters of friends-and-strangers graphs
• Exact upper bound for sorting \(R_n\) with LE
• Sorting on graphs by adjacent swaps using permutation groups

This page was built for publication: A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation

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