The advent of very large scale integrated circuit technology has enabled
the construction of very complex and large interconnection networks. By
most accounts, the next generation of supercomputers will achieve its
gains by increasing the number of processing elements, rather than by
using faster processors. The most difficult technical problem in
constructing a supercom- puter will be the design of the interconnection
network through which the processors communicate. Selecting an
appropriate and adequate topological structure of interconnection
networks will become a critical issue, on which many research efforts
have been made over the past decade. The book is aimed to attract the
readers' attention to such an important research area. Graph theory is a
fundamental and powerful mathematical tool for de- signing and analyzing
interconnection networks, since the topological struc- ture of an
interconnection network is a graph. This fact has been univer- sally
accepted by computer scientists and engineers. This book provides the
most basic problems, concepts and well-established results on the
topological structure and analysis of interconnection networks in the
language of graph theory. The material originates from a vast amount of
literature, but the theory presented is developed carefully and
skillfully. The treatment is gen- erally self-contained, and most stated
results are proved. No exercises are explicitly exhibited, but there are
some stated results whose proofs are left to the reader to consolidate
his understanding of the material.
