This is the authors' abstract. We don't add key points for this paper.
In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O ( n 3/2 √ logn ). By means of the permutation tree, we can improve this algorithm to achieve time complexity O ( nlogn ). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from O ( n 2 ) down to O ( nlogn ).
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Feng et al. (2007) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: