S. Rajasekaran et S. Sahni, SORTING, SELECTION, AND ROUTING ON THE ARRAY WITH RECONFIGURABLE OPTICAL BUSES, IEEE transactions on parallel and distributed systems, 8(11), 1997, pp. 1123-1132
Citations number
31
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
In this paper, we present efficient algorithms for sorting, selection,
and packet routing on the AROB (Array with Reconfigurable Optical Bus
es) model. One of our sorting algorithms sorts n general keys in O(1)
time on an AROB of size n(epsilon) x n for any constant epsilon > 0. W
e also show that selection from out of n elements can be done in rando
mized O(1) time employing n processors. Our routing algorithm can rout
e any h-relation in randomized O(h) time. All these algorithms are cle
arly optimal.