Time-work tradeoffs for parallel algorithms
- 1 September 1997
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 44 (5) , 742-778
- https://doi.org/10.1145/265910.265923
Abstract
Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort, strong connectivity, and and the single source shorest path problem. All of the algorithms run on the EREW PRAM model of parallel computer, except the algorithm for strong connectivity, which runs on the probabilistic EREW PRAM.Keywords
This publication has 8 references indexed in Scilit:
- Parallel dictionaries on 2–3 treesPublished by Springer Nature ,2006
- Parallel Depth-First Search in General Directed GraphsSIAM Journal on Computing, 1990
- An improved parallel algorithm that computes the BFS numbering of a directed graphInformation Processing Letters, 1988
- Towards optimal parallel bucket sortingInformation and Computation, 1987
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- An Efficient Parallel Biconnectivity AlgorithmSIAM Journal on Computing, 1985
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972