Name
Abstract | ||
|---|---|---|
Two sequences of items sorted in increasing order are given: a sequence A of size n and a sequence B of size m. It is required to determine, for every item of A, the smallest item of B (if one exists) that is larger than it. The paper presents two parallel algorithms for the problem. The first algorithm requires O(logm+logn) time using n processors on an EREW PRAM. On an EREW PRAM with p (p⩽min{m, n}) processors, the second algorithm runs in O(logn+p/n) time when m⩽n, or in O(logm+p/n logn/2m) time when m>n. The second algorithm is optimal |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1109/IPPS.1991.153765 | Inf. Process. Lett. |
Keywords | DocType | Volume |
size n,sub n,sequence a,sequence b,erew pram,size m,search problems,computational complexity,parallel algorithms,sup n,parallel multiple search,parallel algorithm,n processor,sub p,binary search | Conference | 37 |
Issue | Citations | PageRank |
4 | 1 | 0.47 |
References | Authors | |
8 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhaofang Wen | 1 | 56 | 8.25 |