Assignment Problems in Parallel and Distributed Computing

This book has been written for practitioners, researchers and stu­ dents in the fields of parallel and distributed computing. Its objective is to provide detailed coverage of the applications of graph theoretic tech­ niques to the problems of matching resources and requirements in multi­ ple computer systems. There has been considerable research in this area over the last decade and intense work continues even as this is being written. For the practitioner, this book serves as a rich source of solution techniques for problems that are routinely encountered in the real world. Algorithms are presented in sufficient detail to permit easy implementa­ tion; background material and fundamental concepts are covered in full. The researcher will find a clear exposition of graph theoretic tech­ niques applied to parallel and distributed computing. Research results are covered and many hitherto unpublished spanning the last decade results by the author are included. There are many unsolved problems in this field-it is hoped that this book will stimulate further research. Front Matter....Pages i-xxiii Introduction....Pages 1-9 Graph-Theoretic Concepts....Pages 11-25 Network Flow Techniques....Pages 27-45 Shortest Path Techniques....Pages 47-69 Varying Load Conditions....Pages 71-93 The Sum-Bottleneck Path Algorithm....Pages 95-116 Mapping for Parallel Processing....Pages 117-134 Conclusions....Pages 135-137 Back Matter....Pages 139-155