Sorting Permutations on an n − Broom

With applications in computer networks, robotics, genetics, data center network optimization, cryptocurrency exchange, transportation and logistics, cloud computing, and social network analysis, the problem of sorting permutations on transposition trees under various operations is highly relevant. The goal of the problem is to sort or rearrange the markers in a predetermined order by swapping them out at the vertices of a tree in the fewest possible swaps. Only certain classes of transposition trees, like path, star, and broom, have computationally efficient algorithms for sorting permutations. In this paper, we examine the so-called n − b r o o m transposition trees. A single broom or simply a b r o o m is a spanning tree formed by joining the center of the star graph with one end of the path graph. A generalized version of a broom known as an n − b r o o m is created by joining the ends of n brooms to one vertex, known as the n − b r o o m center. By using the idea of clear path markers, we present a novel algorithm for sorting permutations on an n − b r o o m for n > 2 that reduces to a novel 2 − b r o o m algorithm and that further reduces to two instances of a 1 − b r o o m algorithm. Our single-broom algorithm is similar to that of Kawahara et al.; however, our proof of optimality for the same is simpler.