Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
SIAM Journal on Computing1988Vol. 17(1), pp. 128–142
Citations Over TimeTop 1% of 1988 papers
Abstract
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.
Related Papers
- → Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA(2012)20 cited
- → Heuristic finite element node numbering(1993)5 cited
- → Numbering Formats for Hierarchic Lists(1982)
- Research on Parcel Numbering Method and Its Implementation(2012)