TY - JOUR
T1 - Approximate parallel scheduling. Part I
T2 - The basic technique with applications to optimal parallel list ranking in logarithmic time
AU - Cole, Richard
AU - Vishkin, Uzi
PY - 1988
Y1 - 1988
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0023952675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023952675&partnerID=8YFLogxK
U2 - 10.1137/0217009
DO - 10.1137/0217009
M3 - Article
AN - SCOPUS:0023952675
SN - 0097-5397
VL - 17
SP - 128
EP - 142
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -