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

DOI10.1016/J.IPL.2016.06.006MaRDI QIDQ2630342zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

permutationsCayley graphsdiametersortingcombinatorial problems

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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

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

Cites work

• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Circular permutations and genome shuffling
• Combinatorics of genome rearrangements.
• Sorting with fixed-length reversals
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The complexity of finding minimum-length generator sequences

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)