Sorting Permutations on an <i>n</i> − <i>Broom</i>

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

Keywords

• sorting permutations
• transposition tree
• <i>broom</i>
• <i>n</i> − <i>broom</i>
• clear path marker
• optimal swap sequence