Optimal Algorithms for Sorting Permutations with Brooms
Loading...
Date
item.page.authors
Journal Title
Journal ISSN
Volume Title
Publisher
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...