Publication Type:

Journal Article


Theoretical Computer Science, Elsevier, Volume 602, p.22-31 (2015)



Cayley graphs, Computational methods, Diameter, Graph theory, Permutations, Prefix transpositions, Sorting, Upper Bound


Permutations are sequences where each symbol in the given alphabet σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a prefix transposition. Transpositions over permutations have applications in genome rearrangements and computer interconnection networks. The set of permutations with n symbols derived from the alphabet σ={0, 1, . . ., n-1} form a symmetric group, that we denote by P<inf>n</inf>. The prefix transposition distance between two permutations π* ∈ P<inf>n</inf> and π ∈P<inf>n</inf> is the minimum number of prefix transpositions, also called moves, needed to transform π* into π . A prefix transposition can be modeled by a permutation operation. A permutation is type of sequence and it is also an operation. The generators for prefix transposition operation are a subset of permutation operation. As a result, transforming an arbitrary π*∈P<inf>n</inf> to an arbitrary π ∈P<inf>n</inf> is equivalent to sorting some π^∈Pn. Thus, upper bound for transforming any π*∈P<inf>n</inf> into any π ∈P<inf>n</inf> with prefix transpositions is simply the upper bound to sort any permutation π∈P<inf>n</inf> with moves. In the article that establishes the best known upper bound for prefix transposition distance over P<inf>n</inf> as n-log<inf>9/2</inf>n, explicit proofs were not given for some cases. In this article, we provide the missing proofs, validating the stated upper bound. Furthermore, we establish an upper bound of n-log<inf>7/2</inf>n for prefix transposition distance over P<inf>n</inf>. © 2015 Published by Elsevier B.V.


cited By 0

Cite this Research Publication

B.a b Chitturi, “Tighter upper bound for sorting permutations with prefix transpositions”, Theoretical Computer Science, vol. 602, pp. 22-31, 2015.