Optimal parallel selection in sorted matrices

Hong Shen, Sarnath Ramnath

研究成果: Article同行評審

3 引文 斯高帕斯(Scopus)

摘要

We present a parallel algorithm running in time O(log m log(Black star) m (log log m + log(n/m))) time and O(m log(n/m)) operations on an EREW PRAM 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 (1992) for selection in a sorted matrix of equal dimensions, and thus answers the open question they posted. The algorithm is work-optimal thus improving upon the result in (Sarnath and He, 1992) for the case of square matrices as well. Our algorithm can be generalized to solve the selection problem on a set of sorted matrices of arbitrary dimensions.

原文English
頁(從 - 到)117-122
頁數6
期刊Information Processing Letters
59
發行號3
DOIs
出版狀態Published - 12 8月 1996
對外發佈

指紋

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

引用此