Back close

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)

Url :

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.

Admissions Apply Now