Selection, routing, and sorting on the star graph

The authors consider the problems of selection, routing and sorting on an n-star graph (with n! n odes), an interconnection network which has been proven to possess many special properties. They identify a tree like subgraph (a `(k, 1, k) chain network´) of the star graph which enables them to design efficient algorithms for these problems. They present an algorithm that performs a sequence of n prefix computations in O(n²) time. This algorithm is used as a subroutine in other algorithms. In addition they offer an efficient deterministic sorting algorithm that runs in (n³ log n)/2 steps. They also show that sorting can be performed on the n-star graph in time O(n³) and that selection of a set of uniformly distributed n keys can be performed in O(n²) time with high probability. Finally, they also present a deterministic (non oblivious) routing algorithm that realizes any permutation in O(n³) steps on the n-star graph