Sorting Permutations with 3-Brooms

The practical applications of sorting permutations using various operations are evident in the fields of genetics and computer interconnection networks. These operations are defined by their respective generator sets, which are sets of elements enabling the manipulation of permutations within a specific group. Specifically, we can represent these operations using a transposition tree, denoted as $T = (V_{T},E_{T})$.In this tree, each edge corresponds to a generator, and the tokens or markers assigned to the vertices are subjected to swapping if the pair of vertices (u, v) exists in the set of edges, denoted as E. The main aim is to arrange the initial configuration, which represents the input permutation, by minimizing the number of swaps or moves required within the transposition tree. In this study, we focus on a particular class of transposition tree called broom, as well as its variation such as single broom and double broom. We defined a transposition tree called 3-broom where the terminal nodes of 3single brooms are connected to a common node. By studying these classes of transposition trees, we came up with some observations that will lead us to design an optimal algorithm for the 3-broom.