Optimal Algorithms for Sorting Permutations with Brooms

Abstract

Transforming permutations with several operations has been extensively studied where newlinea transposition tree is one such operation. Such transformations have applications in newlinegenetics and interconnection networks. In genomic studies, a permutation models a newlinegenome. Likewise, in computer interconnection networks, it denotes a node. The alphabet for permutations is {1, 2, · · · , n and#8722; 1, n} and I = (1, 2, 3, 4, · · · , n and#8722; 1, n) is the newlineidentity permutation. Genomic distance or simply distance between species pertains newlineto the minimum number of generators of a given operation that are required to transform newlineone permutation parsimoniously into another where the first permutation denotes newlinethe source species and the second one denotes the destination species. Likewise, the newlineminimum number of generators of a given operation that are required to transform the newlinesource permutation say and#945; into I is the distance of and#945;. Transforming and#945; into I is called newlinesorting. In computer interconnection networks, the diameter of the underlying Cayley newlinegraph (corresponding to the given operation and the alphabet) gives the maximum newlinelatency between any pair of nodes of the network. Sorting permutations with transposition trees has been well studied. A transposition tree T = (VT ,ET ) is a spanning tree over its vertices. In literature, Sn denotes the symmetric group formed by n symbols. A move of T on a permutation and#960; and#8712; Sn corresponds to any of e and#8712; ET . If e = (i, j) then applying e to and#960; swaps the symbols in positions i and j. Each transposition tree T = (V,E) is an operation where E is the generator set that is closed under inverses. The number f moves that suffice to sort any permutation in Sn with a given T is a upper bound for T. A precise upper bound equals the diameter of the corresponding Cayley graph and#915;, i.e. diam(and#915;). We propose simple and efficient algorithms to compute the distances of permutations with transposition trees broom and a double broom. Aichholzer et al. proved that sorting permutations using transposition trees is NP-hard...

Description

Keywords

Citation

item.page.endorsement

item.page.review

item.page.supplemented

item.page.referenced