APPROXIMATE PARALLEL SCHEDULING .1. THE BASIC TECHNIQUE WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING IN LOGARITHMIC TIME

被引：108

作者：

COLE, R ^{[1
]}

VISHKIN, U ^{[1
]}

机构：

[1] TEL AVIV UNIV,IL-69978 TEL AVIV,ISRAEL

来源：

SIAM JOURNAL ON COMPUTING | 1988年 / 17卷 / 01期

关键词：

Computer Programming--Algorithms - Computer Systems; Digital--Parallel Processing - Mathematical Techniques--Graph Theory;

D O I：

10.1137/0217009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We define a novel scheduling problem; it is solved in parallel by repeated, rapid, approximate reschedulings. This leads to the first optimal logarithmic time PRAM algorithm for list ranking. Companion papers show how to apply these results to obtain improved PRAM upper bounds for a variety of problems on graphs, including the following: connectivity, biconnectivity, Euler tour and st-numbering, and a number of problems on trees.

引用

页码：128 / 142

页数：15

共 25 条

[1] PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].

BRENT, RP .

JOURNAL OF THE ACM, 1974, 21 (02) :201-206

[2] DETERMINISTIC COIN TOSSING WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING [J].

COLE, R ;

VISHKIN, U .

INFORMATION AND CONTROL, 1986, 70 (01) :32-53

[3]

Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P478, DOI 10.1109/SFCS.1986.10

[4]

Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P511, DOI 10.1109/SFCS.1986.41

[5]

COLE R, 1986, 18TH P ANN ACM S THE, P206

[6]

COLE R, 1986, 242 NEW YORK U COUR

[7]

COLE R, UNPUB APPROXIMATE 2

[8]

COLE R, 1986, 209 NEW YORK U COUR

[9]

FISHER M, 1980, J ASSOC COMPUT MACH, V27, P831

[10] EXPLICIT CONSTRUCTIONS OF LINEAR-SIZED SUPERCONCENTRATORS [J].

GABBER, O ;

GALIL, Z .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 22 (03) :407-420

← 1 2 3 →