A Comprehensive Survey on Sorting Permutations using Transposition Tree
S V Ashtapadhi, Devi Pillai, T S Indulekha · 2024
This paper provides a survey on the use of transposition trees for sorting permutations. A permutation can be represented as, π = {n,n − 1,…,1} and its identity as, I = {1,2,…,n − 1,n}. Transforming π to I is termed permutation sorting and it can be done using various operations. A transposition tree is one such operation that offers a structured approach to permutation sorting, facilitating in-depth analysis of permutation structures. A transposition tree T=(VT, ET) is a spanning tree that gives a higher level of abstraction compared to Cayley graphs. We can place Tokens/Markers on vertices and each edge is a transposition. Research in sorting permutations plays a crucial role in simplifying complexities within real-world domains, particularly in areas such as the design of computer interconnection networks and genomic studies. Effective permutation sorting techniques are important for identifying genetic mutations and optimizing network performance. This leads to the emergence of the problems, of finding the distance between the source permutation π and its identity I and finding the diameter of the underlying Cayley graph. Due to the complexities of the underlying Cayley graph, sorting using a transposition tree is an NP-Hard problem. However, optimal solutions are known for certain classes of transposition trees. This paper aims to provide insights into the known classes of transposition trees such as path, star, brooms and their corresponding results for the distance and diameter problems, where available. Additionally, relevant works related to this domain are mentioned to provide a better understanding of advancements in this area.