SORTING, SELECTION, AND ROUTING ON THE ARRAY WITH RECONFIGURABLE OPTICAL BUSES

Authors
RAJASEKARAN S SAHNI S
Citation
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
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
8
Issue
11
Year of publication
1997
Pages
1123 - 1132
Database
ISI
SICI code
1045-9219(1997)8:11<1123:SSAROT>2.0.ZU;2-O
Abstract
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.