دانلود کتاب Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications)

فهرست مطالب :

Cover......Page 1
Title Page......Page 6
Copyright......Page 7
Contents\0......Page 8
Preface\0......Page 10
Notation\0......Page 12
1.1 Preliminaries of Graph Theory\0......Page 18
1.2 Algorithms and Complexities\0......Page 30
1.3 Flows and Cuts\0......Page 37
1.4 Computing Connectivities\0......Page 51
1.5 Representations of Cut Structures\0......Page 62
1.6 Connectivity by Trees\0......Page 74
1.7 Tree Hypergraphs\0......Page 77
2.1 Spanning Subgraphs Preserving Connectivity\0......Page 82
2.2 MA Ordering\0......Page 90
2.3 3-Edge-Connected Components\0......Page 103
2.4 2-Approximation Algorithms for Connectivity\0......Page 117
2.5 Fast Maximum-Flow Algorithms\0......Page 124
2.6 Testing Chordality\0......Page 129
3.1 Pendent Pairs in MA Orderings\0......Page 131
3.2 A Minimum-Cut Algorithm\0......Page 134
3.3 s-Proper k-Edge-Connected Spanning Subgraphs\0......Page 136
3.4 A Hierarchical Structure of MA Orderings\0......Page 140
3.5 Maximum Flows Between a Pendent Pair\0......Page 144
3.6 A Generalization of Pendent Pairs\0......Page 147
3.7 Practically Efficient Minimum-Cut Algorithms\0......Page 148
4.1 Enumerating All Cuts\0......Page 154
4.2 Enumerating Small Cuts\0......Page 157
4.3 Enumerating Minimum Cuts\0......Page 162
4.4 Upper Bounds on the Number of Small Cuts\0......Page 166
5.1 Canonical Forms of Cactus Representations\0......Page 170
5.2 (s, t)-Cactus Representations\0......Page 188
5.3 Constructing Cactus Representations\0......Page 197
6 Extreme Vertex Sets\0......Page 208
6.1 Computing Extreme Vertex Sets in Graphs\0......Page 209
6.2 Algorithm for Dynamic Edges Incident to a Specified Vertex\0......Page 215
6.3 Optimal Contraction Ordering\0......Page 217
6.4 Minimum k-Subpartition Problem\0......Page 224
7.1 Preliminaries\0......Page 234
7.2 Edge Splitting in Weighted Graphs\0......Page 237
7.3 Edge Splitting in Multigraphs\0......Page 243
7.4 Other Splittings\0......Page 249
7.5 Detachments\0......Page 254
7.6 Applications of Splittings\0......Page 257
8 Connectivity Augmentation\0......Page 263
8.1 Increasing Edge-Connectivity by One\0......Page 264
8.2 Star Augmentation\0......Page 266
8.3 Augmenting Multigraphs\0......Page 269
8.4 Augmenting Weighted Graphs\0......Page 271
8.5 More on Augmentation\0......Page 293
9 Source Location Problems\0......Page 299
9.1 Source Location Problem Under Edge-Connectivity Requirements\0......Page 300
9.2 Source Location Problem Under Vertex-Connectivity Requirements\0......Page 312
10.1 Set Functions\0......Page 321
10.2 Minimizing Submodular and Posimodular Functions\0......Page 323
10.3 Extreme Subsets in Submodular and Posimodular Systems\0......Page 332
10.4 Optimization Problems over Submodular and Posimodular Systems\0......Page 337
10.5 Extreme Points of Base Polyhedron\0......Page 353
10.6 Minimum Transversal in Set Systems\0......Page 359
Bibliography\0......Page 374
Index\0......Page 388