REFERENCES 281Tarjan, R. “Depth-First Search and Linear Graph Algorithms,” SIAM Journal
on Computing, 1(2), pp. 146–160, 1972.
Chapter 7. Parallel Algorithms
Akl, S. Parallel Sorting. Academic Press, Orlando, FL, 1985.
Akl, S. The Design and Analysis of Parallel Algorithms. Prentice Hall, Englewood
Cliffs, NJ, 1989.
Fortune, S. and Wyllie, J. “Parallelism in Random Access Machines,” Proceedings
of the Tenth Annual ACM Symposium on Theory of Computing, pp. 114–118,
1978.
Goldschlager, L. “A Unified Approach to Models of Synchronous Parallel
Machines,” Proceedings of the Tenth Annual ACM Symposium on Theory of Com-
puting, pp. 89–94, 1978.
Greenlaw, R., Hoover, H., and Ruzzo, W. Limits to Parallel Computation: P-
Completeness Theory. Oxford University Press, New York, 1995.
Karp, R. and Ramachandran, V. “A Survey of Parallel Algorithms and Shared
Memory Machines,” in vanLeeuwen, A. (ed.), Handbook of Theoretical Com-
puter Science: Algorithms and Complexity, pp. 869–941. Elsevier, New York,
1990.
Kruskal, C. “Searching, Merging, and Sorting in Parallel Computation,” IEEE
Transactions on Computers, 32(10), pp. 942–946, 1983.
Leighton, F. Introduction to Parallel Algorithms and Architectures: Arrays, Trees,
Hypercubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.
Miller, R. and Boxer, L. A Unified Approach to Sequential and Parallel Algorithms.
Prentice Hall, Inc., Upper Saddle River, NJ, 2000.
Miller, R. and Stout, Q. Parallel Algorithms for Regular Architectures: Meshes and
Pyramids. The MIT Press, Cambridge, MA, 1996.
Quinn, M. and Deo, N. “Parallel Graph Algorithms,” ACM Computing Surveys,
16(3), pp. 319–348, 1984.
Shiloach, Y. and Vishkin, U. “Finding the Maximum, Merging, and Sorting in
a Parallel Computation Model,” Journal of Algorithms, 2, pp. 88–102, 1981.
Chapter 8. Nondeterministic Algorithms
Cook, S. “The Complexity of Theorem Proving Procedures,” Proceedings of the
Third Annual ACM Symposium on Theory of Computing, pp. 151–158, 1971.
Garey, M. and Johnson, D. Computers and Intractability: A Guide to the Theory of
NP- Completeness. W. H. Freeman, San Francisco, CA, 1979.