SELECTION, ROUTING, AND SORTING ON THE STAR GRAPH

We consider the problems of selection, routing, and sorting on an n-st ar graph (with n! nodes), an interconnection network which has been pr oven to possess many special properties. We identify a tree like subgr aph (which we call a ''(k, 1, k) chain network'') of the star graph wh ich enables us to design efficient algorithms for the above mentioned problems, We present an algorithm that performs a sequence of n prefix computations in O(n(2)) time, This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on the It-star graph in time O(n(3)) and that selection of a set of unif ormly distributed n keys can be performed in O(n(2)) time with high pr obability, Finally, we also present a deterministic (nonoblivious) rou ting algorithm that realizes any permutation in O(n(3)) steps on the n -star graph, There exists an algorithm in the literature that can perf orm a single prefix computation in O(n Ig n) time. The best-known prev ious algorithm for sorting has a run time of O(n(3) Ig n) and is deter ministic, To our knowledge, the problem of selection has not been cons idered before on the star graph. (C) 1997 Academic Press.