Publication

Abstract : 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 𝑛−𝑏𝑟𝑜𝑜𝑚𝑛−𝑏𝑟𝑜𝑜𝑚 transposition trees. A single broom or simply a 𝑏𝑟𝑜𝑜𝑚𝑏𝑟𝑜𝑜𝑚 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 𝑛−𝑏𝑟𝑜𝑜𝑚𝑛−𝑏𝑟𝑜𝑜𝑚 is created by joining the ends of n brooms to one vertex, known as the 𝑛−𝑏𝑟𝑜𝑜𝑚𝑛−𝑏𝑟𝑜𝑜𝑚 center. By using the idea of clear path markers, we present a novel algorithm for sorting permutations on an 𝑛−𝑏𝑟𝑜𝑜𝑚𝑛−𝑏𝑟𝑜𝑜𝑚 for 𝑛>2𝑛>2 that reduces to a novel 2−𝑏𝑟𝑜𝑜𝑚2−𝑏𝑟𝑜𝑜𝑚 algorithm and that further reduces to two instances of a 1−𝑏𝑟𝑜𝑜𝑚1−𝑏𝑟𝑜𝑜𝑚 algorithm. Our single-broom algorithm is similar to that of Kawahara et al.; however, our proof of optimality for the same is simpler.