Algorithmic Aspects of Graph Connectivity is the first comprehensive book on this central notion in graph and network theory, emphasizing its algorithmic aspects. Because of its wide applications in the fields of communication, transportation, and production, graph connectivity has made tremendous algorithmic progress under the influence of the theory of complexity and algorithms in modern computer science. The book contains various definitions of connectivity, including edge-connectivity and vertex-connectivity, and their ramifications, as well as related topics such as flows and cuts. The authors comprehensively discuss new concepts and algorithms that allow for quicker and more efficient computing, such as maximum adjacency ordering of vertices. Covering both basic definitions and advanced topics, this book can be used as a textbook in graduate courses in mathematical sciences, such as discrete mathematics, combinatorics, and operations research, and as a reference book for specialists in discrete mathematics and its applications.
Author(s): Hiroshi Nagamochi, Toshihide Ibaraki
Series: Encyclopedia of Mathematics and its Applications
Publisher: CUP
Year: 2008
Language: English
Pages: 392
Cover......Page 1
Title Page......Page 6
Copyright......Page 7
Contents ......Page 8
Preface ......Page 10
Notation ......Page 12
1.1 Preliminaries of Graph Theory ......Page 18
1.2 Algorithms and Complexities ......Page 30
1.3 Flows and Cuts ......Page 37
1.4 Computing Connectivities ......Page 51
1.5 Representations of Cut Structures ......Page 62
1.6 Connectivity by Trees ......Page 74
1.7 Tree Hypergraphs ......Page 77
2.1 Spanning Subgraphs Preserving Connectivity ......Page 82
2.2 MA Ordering ......Page 90
2.3 3-Edge-Connected Components ......Page 103
2.4 2-Approximation Algorithms for Connectivity ......Page 117
2.5 Fast Maximum-Flow Algorithms ......Page 124
2.6 Testing Chordality ......Page 129
3.1 Pendent Pairs in MA Orderings ......Page 131
3.2 A Minimum-Cut Algorithm ......Page 134
3.3 s-Proper k-Edge-Connected Spanning Subgraphs ......Page 136
3.4 A Hierarchical Structure of MA Orderings ......Page 140
3.5 Maximum Flows Between a Pendent Pair ......Page 144
3.6 A Generalization of Pendent Pairs ......Page 147
3.7 Practically Efficient Minimum-Cut Algorithms ......Page 148
4.1 Enumerating All Cuts ......Page 154
4.2 Enumerating Small Cuts ......Page 157
4.3 Enumerating Minimum Cuts ......Page 162
4.4 Upper Bounds on the Number of Small Cuts ......Page 166
5.1 Canonical Forms of Cactus Representations ......Page 170
5.2 (s, t)-Cactus Representations ......Page 188
5.3 Constructing Cactus Representations ......Page 197
6 Extreme Vertex Sets ......Page 208
6.1 Computing Extreme Vertex Sets in Graphs ......Page 209
6.2 Algorithm for Dynamic Edges Incident to a Specified Vertex ......Page 215
6.3 Optimal Contraction Ordering ......Page 217
6.4 Minimum k-Subpartition Problem ......Page 224
7.1 Preliminaries ......Page 234
7.2 Edge Splitting in Weighted Graphs ......Page 237
7.3 Edge Splitting in Multigraphs ......Page 243
7.4 Other Splittings ......Page 249
7.5 Detachments ......Page 254
7.6 Applications of Splittings ......Page 257
8 Connectivity Augmentation ......Page 263
8.1 Increasing Edge-Connectivity by One ......Page 264
8.2 Star Augmentation ......Page 266
8.3 Augmenting Multigraphs ......Page 269
8.4 Augmenting Weighted Graphs ......Page 271
8.5 More on Augmentation ......Page 293
9 Source Location Problems ......Page 299
9.1 Source Location Problem Under Edge-Connectivity Requirements ......Page 300
9.2 Source Location Problem Under Vertex-Connectivity Requirements ......Page 312
10.1 Set Functions ......Page 321
10.2 Minimizing Submodular and Posimodular Functions ......Page 323
10.3 Extreme Subsets in Submodular and Posimodular Systems ......Page 332
10.4 Optimization Problems over Submodular and Posimodular Systems ......Page 337
10.5 Extreme Points of Base Polyhedron ......Page 353
10.6 Minimum Transversal in Set Systems ......Page 359
Bibliography ......Page 374
Index ......Page 388
