Approximate and exact parallel scheduling with applications to list, tree and graph problems
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 478-491
- https://doi.org/10.1109/sfcs.1986.10
Abstract
We study two parallel scheduling problems and their use in designing parallel algorithms. First, we define a novel scheduling problem; it is solved by repeated, rapid, approximate reschedulings. This leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time. Our second scheduling result is for computing prefix sums of logn bit numbers. We give an optimal parallel algorithm for the problem which runs in sublogarithmic time. These two scheduling results together lead to logarithmic time PRAM algorithms for the connectivity, biconnectivity and minimum spanning tree problems. The connectivity and biconnectivity algorithms are optimal unless m = o(nlog*n), in graphs of n vertices and m edges.Keywords
This publication has 11 references indexed in Scilit:
- Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithmsPublished by Association for Computing Machinery (ACM) ,1986
- An Efficient Parallel Biconnectivity AlgorithmSIAM Journal on Computing, 1985
- On efficient parallel strong orientationInformation Processing Letters, 1985
- Expanders obtained from affine transformationsPublished by Association for Computing Machinery (ACM) ,1985
- An optimal parallel algorithm for integer sortingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parallel tree contraction and its applicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- An optimal parallel connectivity algorithmDiscrete Applied Mathematics, 1984
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974