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 separations, while the main focus of the book is on techniques for deriving lower bounds on the sizes of graph separators. This asymmetry in focus reflects our perception that the work on upper bounds, or algorithms, for graph separation is much better represented in the standard theory literature than is the work on lower bounds, which we perceive as being much more scattered throughout the literature on application areas. Given the multitude of notions of graph separator that have been developed and studied over the past (roughly) three decades, there is a need for a central, theory-oriented repository for the mass of results. The need is absolutely critical in the area of lower-bound techniques for graph separators, since these techniques have virtually never appeared in articles having the word `separator' or any of its near-synonyms in the title. Graph Separators with Applications fills this need.
Author(s): Rosenberg A., Heath L.
Series: Frontiers in Computer Science
Publisher: Kluwer
Year: 2002
Language: English
Pages: 270
Tags: Математика;Дискретная математика;Теория графов;
Cover......Page 1
Title......Page 4
Preface......Page 6
Contents......Page 12
1.1. Introduction......Page 14
1.2. Basic Notions and Notation......Page 15
1.3. Interesting Graph Families......Page 17
1.4. Graph Separators......Page 25
1.5. Graph Embeddings......Page 40
1.6. Quasi-Isometric Graph Families......Page 46
1.7. Sources......Page 57
2.1. Introduction......Page 60
2.2. Nonserial Dynamic Programming......Page 62
2.3. Graph Embeddings via Separators......Page 66
2.4. Laying Out VLSI Circuits......Page 81
2.5. Strongly Universal Interval Hypergraphs......Page 95
2.6. Pebbling Games: Register Allocation and Processor Scheduling......Page 105
2.7. Sources......Page 107
3.1. Introduction......Page 112
3.2. NP-Completeness......Page 114
3.3. Topological Approaches to Graph Separation......Page 122
3.4. Geometric Approaches to Graph Separation......Page 134
3.5. Network Flow Approaches to Graph Separation......Page 143
3.6. Heuristic Approaches to Graph Separation......Page 160
3.7. Sources......Page 169
4.1. Overview of Lower-Bound Techniques......Page 172
4.2. Packing Arguments for Bounding Separation-Width......Page 175
4.3. Congestion Arguments for Bounding Separation-Width......Page 201
4.4. A Technique for Complete Trees......Page 222
4.5. Information-Transfer Arguments......Page 231
4.6. Sources......Page 236
A.2. Graph Embeddings via Separators......Page 240
A.3. Laying Out VLSI Circuits......Page 245
A.4. Strongly Universal Interval Hypergraphs......Page 248
A.5. Pebbling Games......Page 252
A.6. Sources......Page 253
Bibliography......Page 254
About the Authors......Page 264
C......Page 266
G......Page 267
M......Page 268
R......Page 269
Z......Page 270
