Communication Complexity and Parallel Computing
By: by Juraj Hromkovič
Series: Texts in Theoretical Computer Science An EATCS Series; Texts in Theoretical Computer Science An EATCS Series
Publisher: Springer Berlin Heidelberg
Published: 1997
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] /
Number of pages: 338
ISBN-13: 9783642081859; 9783662034422
Subjects: Computer Communication Networks; Telecommunication; Mathematics; Electronics; Computer science; Data transmission systems
Description: This book is devoted to the investigation of a special topic in theoretical computer science - communication complexity as an abstract measure of the complexity of computing problems. Its main aim is to show how the theoretical study of communication complexity can be useful in the process of designing effective parallel algorithms. The author shows how to get important information about the parallel complexity (parallel time, the number of processors, the descriptional complexity of the topology of the parallel architecture) of specific computing problems from knowledge of their communication complexity. The book is written as a textbook for undergraduate and graduate students and provides a careful explanation of the subject as well as motivation for further research.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.
Table of contents: title: From the contents: Introduction; title: Communication Protocol Models; title: Boolean Circuits; title: VLSI Circuits and Interconnection Networks; title: Sequential Computations.