Routing, Broadcasting, Prefix Sums, and Sorting Algorithms on the Arrangement Graph
Yifeng Li, Ke Qiang Qiu · 2009
The arrangement graph is a generalization of the well known star graph and the alternating group graph. We first resent a constant time routing algorithm that allows two groups of sub-arrangement graphs to exchange their data in a one-to-one fashion. We then use this routing algorithm to develop an optimal broadcasting algorithm, an optimal algorithm for computing the general prefix sums as well as an efficient sorting algorithm on the arrangement graph. Consequently, all of our algorithms are applicable to the star and the alternating group graphs.