Sorting permutations with transpositions in O(n3) amortized time
| Autor: | Bhadrachalam Chitturi, Priyanshu Das |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Amortized analysis
General Computer Science Cayley graph Transposition (telecommunications) Sorting Block (permutation group theory) Theoretical Computer Science Combinatorics Permutation Symmetric group TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Data_FILES Suffix MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Theoretical Computer Science. 766:30-37 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2018.09.015 |
| Popis: | The problem of sorting a permutation π over alphabet ∑ = { 1 , 2 , 3 … n } with the minimum number of transpositions is known to be intractable. That is, the computation of transposition distance i.e. d t ( π ) , is hard. Such sorting is equivalent to determining the distance between any α, β of the symmetric group Sn over ∑ under the transposition operation. It has applications in computer interconnection networks where a node is denoted by a permutation, and genetics where a genome is modeled by a permutation. The maximum distance between any pair of permutations in Sn is the diameter i.e. diam( Γ ( S n ) ), of the corresponding Cayley graph Γ ( S n ) . It corresponds to the maximum latency in the computer interconnection network modeled by Γ ( S n ) and the maximum genetic dissimilarity between any pair α, β in Sn. We call transpositions, prefix transpositions, suffix transpositions and prefix/suffix transpositions as block-moves. We design an algorithm to compute d t ( π ) ∀π in Sn and compute diam( Γ ( S n ) ) with transpositions in O ( n ! n 3 ) time and O ( n ! n 2 ) space; at an amortized time of O ( n 3 ) . The same can be computed for the remaining block moves in O ( n 2 log n ) amortized time and O ( n ! n ) space. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect