Graph Separators, with Applications
Graph Separators with Applications is devoted to techniques for obtaining upper and lower bounds on the sizes of graph separators - upper bounds being obtained via decomposition algorithms. The book surveys the main approaches to obtaining good graph sepa
- PDF / 15,966,859 Bytes
- 267 Pages / 461.008 x 714.632 pts Page_size
- 23 Downloads / 287 Views
FRONTIERS OF COMPUTER SCIENCE Series Editor: Arnold L. Rosenberg University of Massachusetts Amherst, Massachusetts ASSOCIATIVE COMPUTING: A Programming Paradigm for Massively Parallel Computers Jerry L. Potter INTRODUCTION TO PARALLEL AND VECTOR SOLUTION OF LINEAR SYSTEMS James M. Ortega PARALLEL EVOLUTION OF PARALLEL PROCESSORS (A book in the Surveys in Computer Science series, Edited by Larry Rudolph) Gil Lerman and Larry Rudolph GRAPH SEPARATORS, WITH APPLICATIONS Arnold L. Rosenberg and Lenwood S. Heath
A Continuation Order Plan is available for this series. A continuation order will bring delivery of each new volume immediately upon publication. Volumes are billed only upon actual shipment. For further information please contact the publisher.
Graph Separators, with Applications Arnold L. Rosenberg University of Massachusetts Amherst, Massachusetts
and
Lenwood S. Heath Virginia Polytechnic Institute Blacksburg, Virginia
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
H%RRN ,6%1 3ULQW,6%1
0-306-46977-4 0-306-46464-0
.OXZHU$FDGHPLF3XEOLVKHUV 1HZ 0.
A.2. • Graph Embeddings via Separators
231
VERIFICATION. We merely suggest how one evaluates the relevant summations. For X-trees:
For meshes:
For hypercubes:
The indicated summations can be adequately estimated via integration. Details are left to the reader.
The bounds of Application A.2.6 are within constant factors of optimal. To wit:
• The embedding of the N-node X-tree into the path, which is induced by the inorder embedding of the complete binary tree, has average dilation proportional to log N. • The row-major embedding of the mesh into the path has average dilation • The recursive, dimension-by-dimension, embedding of the N-node boolean hypercube into the path has average dilation N/2.
A.2.3.2. Meshes
Our final example points out that the cumulative-cost of embeddings of boolean hypercubes into two-dimensional meshes is just a factor of 2 smaller than the cumulative-cost of embeddings of hypercubes into paths.
232
Appendix A • Applications of Graph Separators, Revisited
We leave the verification of the following to the reader.
APPLICATION A.2.7. The cumulative-cost of any embedding of the N-node boolean hypercube into the N-node two-dimensional mesh is no smaller
than
for some constant c > 0.
A.3. Laying Out VLSI Circuits We remarked in Section 2.4 that the abstract VLSI layouts produced by the strategy presented there are often within a constant factor of optimal in AREA rather than just within a few logarithmic factors of optimal. In this
section we exhibit three families of graphs that illustrate our point, namely, boolean hypercubes, FFT graphs, and multidimensional meshes. In all three cases we sketch how to establish the upper bounds using the layout strategy of Section 2.4.1 (but using simple recursive edge-bisectors that the families admit, rather than bifurcators), and we invoke Chapter 4’s bounds on bisection-width to allow us to instantiate the lower-bound technique of Section 2.4.2.
Data Loading...
