Efficient parallel algorithms for selection and searching on sorted matrices
Authors:
- Xin HeXHXin He
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 34, 108-111
Abstract
Parallel algorithms for more general versions of the well known selection and searching problems are formulated. The authors look at these problems when the set of elements can be represented as an n*n matrix with sorted rows and columns. The selection algorithm takes O(lognloglogn log* n) time with O(n/log nlog* n) processors on an EREW PRAM. The searching algorithm takes O(loglogn) time with O(n/loglogn) processors on a CREW PRAM, which is optimal. The authors also show that no algorithm using at most n log/sup c/ n processors, c>or=1, can solve the matrix search problem in time faster than Omega (log log n).<>Keywords
This publication has 8 references indexed in Scilit:
- An optimally efficient selection algorithmInformation Processing Letters, 1988
- Routing, merging, and sorting on parallel models of computationJournal of Computer and System Sciences, 1985
- Generalized Selection and Ranking: Sorted MatricesSIAM Journal on Computing, 1984
- Polynomially bounded algorithms for locatingp-centers on a treeMathematical Programming, 1982
- The Science of Programming1981
- An Algorithmic Approach to Network Location Problems. II: Thep-MediansSIAM Journal on Applied Mathematics, 1979
- Finding the medianJournal of Computer and System Sciences, 1976
- Estimates of Location Based on Rank TestsThe Annals of Mathematical Statistics, 1963