Volume I: Fundamentals of Parallel Computation
R. Greenlaw, H. J. Hoover, S. Miyano
W. L. Ruzzo, S. Shiraishi, T. Shoudai
Volume I consists of material from Greenlaw, Hoover,
and Ruzzo's book Limits to Parallel Computation: P-completeness
Theory and Miyano's book
P-Completeness and Efficient Parallelization.
Table of Contents for Part A
-
Introduction
-
Parallel Models of Computation
-
Complexity
-
Two Basic P-Complete Problems
-
Evidence that P Does Not Equal NC
-
The Circuit Value Problem
-
Greedy Algorithms
-
P-Complete Algorithms
-
Two Other Notions of P-Completeness
-
Approximating P-Complete Problems
-
Remarks
Table of Contents for Part B
-
Preliminaries on Complexity Theory
-
Efficient Parallel Algorithms
-
Hardness of Efficient Parallelization
-
Typical P-Complete Problems
-
Efficient Parallelization
This site is maintained by Ray.
Last update: 1/12/2001