DETERMINISTIC PARALLEL LIST RANKING

被引：0

作者：

ANDERSON, RJ ^{[1
]}

MILLER, GL ^{[1
]}

机构：

[1] UNIV SO CALIF,DEPT COMP SCI,LOS ANGELES,CA 90089

来源：

ALGORITHMICA | 1991年 / 6卷 / 06期

关键词：

LIST RANKING; PARALLEL ALGORITHMS; LIST TRAVERSAL;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on an EREW PRAM with n/log n processors. The algorithm matches the performance of the Cole-Vishkin [CV3] algorithm but is simple and has reasonable constant factors.

引用

页码：859 / 868

页数：10

共 15 条

[1] DETERMINISTIC COIN TOSSING WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING
COLE, R
VISHKIN, U
[J]. INFORMATION AND CONTROL, 1986, 70 (01): : 32 - 53
[2] FASTER OPTIMAL PARALLEL PREFIX SUMS AND LIST RANKING
COLE, R
VISHKIN, U
[J]. INFORMATION AND COMPUTATION, 1989, 81 (03) : 334 - 352
[3] APPROXIMATE PARALLEL SCHEDULING .1. THE BASIC TECHNIQUE WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING IN LOGARITHMIC TIME
COLE, R
VISHKIN, U
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (01) : 128 - 142
[4] THE ACCELERATED CENTROID DECOMPOSITION TECHNIQUE FOR OPTIMAL PARALLEL TREE EVALUATION IN LOGARITHMIC TIME
COLE, R
VISHKIN, U
[J]. ALGORITHMICA, 1988, 3 (03) : 329 - 346
[5] GAZIT H, 1986, OPTIMAL TREE CONTRAC
[6] GOLDBERG AV, 1987, 19TH P ANN ACM S THE, P315
[7] HAN Y, 1987, THESIS DUKE U
[8] KOSARAJU SR, 1988, AEGEAN WORKSHOP COMP, P101
[9] KRUSKAL CP, 1985, 1985 P INT C PAR PRO, P180
[10] Miller G. L., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P478, DOI 10.1109/SFCS.1985.43

← 1 2 →