**Paperback**|

**$23.00 Short**|

**£15.95**| ISBN: 9780262621786 | 112 pp. | March 2003

## Look Inside

## Complexity Issues in VLSI

## Overview

This book solves several mathematical problems in the areas of Very Large Scale Integration (VLSI) and parallel computation. In particular, it describes optimal layouts for the shuffle-exchange graph, one of the best known networks for parallel computation. Attempts to design a shuffle-exchange computer have been hampered in part by the fact that, until now, no good layouts for the shuffle-exchange graph were known.

The mesh of trees network (which may eventually prove as useful as the shuffle-exchange graph) is introduced and the book shows how it can be used to perform a variety of computations, including sorting and matrix multiplication, in a logarithmic number of steps.

Next, the book introduces the tree of meshes, the first planar graph that was discovered not to have a linear-area layout. Most recently, the structure of this graph has been used to develop a general framework for solving VLSI graph layout problems.

Finally, the book develops techniques for proving lower bounds on the bisection width, crossing number, and layout area of a graph. These techniques significantly extend the power and range of previous methods.

Researchers in the fields of VLSI, parallel computation, and graph theory will find this study of particular value; it is also accessible to anyone with an elementary knowledge of mathematics and computer science. The book is self-contained and presents in a unified and original manner many results scattered in the technical literature, while also covering new and fundamental results for the first time.

## About the Author

Tom Leighton is Assistant Professor of Mathematics in the Department of Applied Mathematics and Laboratory for Computer Science at MIT.