This book provides a comprehensive analysis of the most important topics in parallel computation. It is written so that it may be used as a self-study guide to the field, and researchers in parallel computing will find it a useful reference for many years to come. The first half of the book consists of an introduction to many fundamental issues in parallel computing. The second half provides lists of P-complete- and open problems. These lists will have lasting value to researchers in both industry and academia. The lists of problems, with their corresponding remarks, the thorough index, and the hundreds of references add to the exceptional value of this resource. While the exciting field of parallel computation continues to expand rapidly, this book serves as a guide to research done through 1994 and also describes the fundamental concepts that new workers will need to know in coming years. It is intended for anyone interested in parallel computing, including senior level undergraduate students, graduate students, faculty, and people in industry. As an essential reference, the book will be needed in all academic libraries.
Author(s): Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo
Publisher: Oxford University Press, USA
Year: 1995
Language: English
Pages: 328
Preface......Page 8
Contents......Page 14
Part I: Background and Theory......Page 18
1 Introduction......Page 20
2 Parallel Models of Computation......Page 36
3 Complexity......Page 55
4 Two Basic P-Complete Problems......Page 74
5 Evidence That NC Does Not Equal P......Page 78
6 The Circuit Value Problem......Page 88
7 Greedy Algorithms......Page 104
8 P-Complete Algorithms......Page 111
9 Two Other Notions of P-Completeness......Page 117
10 Approximating P-Complete Problems......Page 125
Part II: A Compendium of Problems......Page 134
P-Complete Problems......Page 136
A.1 Circuit Complexity......Page 138
A.2 Graph Theory......Page 145
A.3 Searching Graphs......Page 161
A.4 Combinatorial Optimization......Page 167
A.5 Local Optimality......Page 175
A.6 Logic......Page 184
A.7 Formal Languages......Page 193
A.8 Algebra......Page 202
A.9 Geometry......Page 218
A.10 Real Analysis......Page 223
A.11 Games......Page 225
A.12 Miscellaneous......Page 232
Open Problems......Page 238
Notation......Page 261
Complexity Classes......Page 264
Bibliography......Page 272
Problem List......Page 302
Index......Page 308
