## A new upper bound for sorting permutations with prefix transpositions

Publication Type : Journal Article

Publisher : Discrete Mathematics, Algorithms and Applications, World Scientific

Source : Discrete Mathematics, Algorithms and Applications, World Scientific, Volume 12, Issue 06, p.2050077 (2020)

Keywords : Cayley graphs, Diameter, Permutations, prefix transposition, Sorting, Upper Bound

Campus : Amritapuri

School : School of Arts and Sciences

Department : Mathematics

Year : 2020

Abstract : Permutations are discrete structures that naturally model a genome where every gene occurs exactly once. In a permutation over the given alphabet ΣΣ, each symbol of ΣΣ appears exactly once. A transposition operation on a given permutation ππ exchanges two adjacent sublists of ππ. If one of these sublists is restricted to be a prefix then one obtains a prefix transposition. The symmetric group of permutations with nn symbols derived from the alphabet Σ={0,1,2,…,(n−1)}Σ={0,1,2,…,(n−1)} is denoted by SnSn. The symmetric prefix transposition distance between π⋆∈Snπ⋆∈Sn and π#∈Snπ#∈Sn is the minimum number of prefix transpositions that are needed to transform π⋆π⋆ into π#π#. It is known that transforming an arbitrary π⋆∈Snπ⋆∈Sn into an arbitrary π#∈Snπ#∈Sn is equivalent to sorting some π′∈Snπ′∈Sn. Thus, upper bound for transforming any π⋆∈Snπ⋆∈Sn into any π#∈Snπ#∈Sn with prefix transpositions is simply the upper bound to sort any permutation π∈Snπ∈Sn. The current upper bound is n−log(72)nn−log(72)n for prefix transposition distance over SnSn. In this paper, we improve the same to n−log3nn−log3n.

Cite this Research Publication : Pramod P. Nair, Sundaravaradhan, R., and Chitturi, B., “A new upper bound for sorting permutations with prefix transpositions”, Discrete Mathematics, Algorithms and Applications, vol. 12, no. 06, p. 2050077, 2020.