Generalized parallel selection in sorted matrices

Hong Shen

研究成果: Conference article同行評審

2 引文 斯高帕斯(Scopus)


This paper presents a parallel algorithm running in time O(log m log* m(log log m+log(n/m))) time on an EREW PRAM with O(m/(log m log* m)) processors for the problem of selection in an m×n matrix with sorted rows and columns, m≤n. Our algorithm generalizes the result of Sarnath and He for selection in a sorted matrix of equal dimensions, and thus answers the open question they posted. The algorithm is work-optimal when n≥m log m, and near optimal within O(log log m) factor otherwise. We show that our algorithm can be generalized to solve the selection problem on a set of sorted matrices of arbitrary dimensions.

頁(從 - 到)281-285
期刊IEEE Symposium on Parallel and Distributed Processing - Proceedings
出版狀態Published - 1996
事件Proceedings of the 1996 8th IEEE Symposium on Parallel and Distributed Processing - New Orleans, LA, USA
持續時間: 23 10月 199626 10月 1996


深入研究「Generalized parallel selection in sorted matrices」主題。共同形成了獨特的指紋。