Analysis of Algorithm D* on N-Broom

The study of transforming permutations using various operations, including transposition trees, has garnered significant attention due to its applications in diverse fields such as genetics and interconnection networks. Permutations are commonly employed to model genomes in genomic studies, while in computer interconnection networks, they represent nodes. This area of research has played a crucial role in enhancing our understanding of genetic processes and optimizing network designs. The symmetric group formed by n symbols is denoted as S
n
. The upper bound for the number of moves required to sort any permutation in S
n
using a transposition trees is determined by the diameter of the corresponding Cayley graph, denoted as diam (Γ). Jerrum showed that computing the diameter of Γ, Cayley graph becomes computationally challenging when the number of generators is at least two. Consequently, there is a strong interest in finding tighter upper bounds for transposition trees, both from theoretical and practical perspectives. Here we show that δ
^*
gives the tighter upper bound for the class of trees called n-brooms.