Preliminary versionA preliminary version of these results was presented in:
- Thomas H. Spencer. Time-work tradeoffs for parallel graph algorithms. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 425-432, San Francisco, California, 28-30 January 1991.
- T. H. Spencer. More time-work tradeoffs for parallel graph algorithms. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 81-94, Hilton Head, South Carolina, July 1991. ACM Press.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms
General Terms: Algorithms, Theory, Parallel Computation
Additional Key Words and Phrases: Breadth first search, PRAM, nearby lists, shortest path, topological sort, transitive colsure
Selected references
- Alok Aggarwal, Richard J. Anderson, and Ming-Yang Kao. Parallel depth-first search in general directed graphs. SIAM Journal on Computing, 19(2):397-409, April 1990.
- Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-206, April 1974.
- Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 1-6, New York City, 25-27 May 1987.
- Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, July 1987.
- Zvi Galil. Optimal parallel algorithms for string matching. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 240-248, Washington, D.C., 1984.
- Hillel Gazit and Gary L. Miller. An improved parallel algorithm that computes the BFS numbering of a directed graph. Information Processing Letters, 28(2):61-65, 24 June 1988.
- Torben Hagerup. Towards optimal parallel bucket sorting. Information and Computation, 75(1):39-51, October 1987.
- Philip N. Klein and S. Sairam. A parallel randomized approximation scheme for shortest paths. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 750-758, Victoria, British Columbia, Canada, 4-6 May 1992.
- Wolfgang J. Paul, Uzi Vishkin, and Hubert Wagener. Parallel dictionaries in 2-3 trees. In Josep Díaz, editor, Automata, Languages and Programming, 10th Colloquium, volume 154 of Lecture Notes in Computer Science, pages 597-609, Barcelona, Spain, 18-22 July 1983. Springer-Verlag.
- John H. Reif. An optimal parallel algorithm for integer sorting. In 26th Annual Symposium on Foundations of Computer Science, pages 496-504, Portland, Oregon, 21-23 October 1985. IEEE.
- Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, June 1972.
- Robert E. Tarjan and Uzi Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, November 1985.
- J. Ullman and M. Yannakakis. High-probability parallel transitive closure algorithms. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 200-209, Island of Crete, Greece, July 1990. ACM Press.