Optimal Selection on Non-partitionable Superposed Parallel Buses

Abstract:

This paper presents an optimal selection algorithm on nxn non-partitionable superposed parallel buses. For arbitrary k (1 leq k leq n2) we can find the k-th smallest item in O(n) time on nxn processors, where each processor has one data item, and is connected to row and column buses. This performance is shown
to be optimal within a constant factor. This algorithm is non-adaptive in the sense that the algorithm does not depend on the data items to select. The algorithm can be adapted to a mesh-connected computer with the same asymptotic time performance.