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.