Algorithmic Aspects of Graph ConnectivityPDF电子书下载

1 Introduction 1

1.1 Preliminaries of Graph Theory 1

1.2 Algorithms and Complexities 13

1.3 Flows and Cuts 20

1.4 Computing Connectivities 34

1.5 Representations of Cut Structures 45

1.6 Connectivity by Trees 57

1.7 Tree Hypergraphs 60

2 Maximum Adjacency Ordering and Forest Decompositions 65

2.1 Spanning Subgraphs Preserving Connectivity 65

2.2 MA Ordering 73

2.3 3-Edge-Connected Components 86

2.4 2-Approximation Algorithms for Connectivity 100

2.5 Fast Maximum-Flow Algorithms 107

2.6 Testing Chordality 112

3 Minimum Cuts 114

3.1 Pendent Pairs in MA Orderings 114

3.2 A Minimum-Cut Algorithm 117

3.3 s-Proper k-Edge-Connected Spanning Subgraphs 119

3.4 A Hierarchical Structure of MA Orderings 123

3.5 Maximum Flows Between a Pendent Pair 127

3.6 A Generalization of Pendent Pairs 130

3.7 Practically Efficient Minimum-Cut Algorithms 131

4 Cut Enumeration 137

4.1 Enumerating All Cuts 137

4.2 Enumerating Small Cuts 140

4.3 Enumerating Minimum Cuts 145

4.4 Upper Bounds on the Number of Small Cuts 149

5 Cactus Representations 153

5.1 Canonical Forms of Cactus Representations 153

5.2 （s，t）-Cactus Representations 171

5.3 Constructing Cactus Representations 180

6 Extreme Vertex Sets 191

6.1 Computing Extreme Vertex Sets in Graphs 192

6.2 Algorithm for Dynamic Edges Incident to a Specified Vertex 198

6.3 Optimal Contraction Ordering 200

6.4 Minimum k-Subpartition Problem 207

7 Edge Splitting 217

7.1 Preliminaries 217

7.2 Edge Splitting in Weighted Graphs 220

7.3 Edge Splitting in Multigraphs 226

7.4 Other Splittings 232

7.5 Detachments 237

7.6 Applications of Splittings 240

8 Connectivity Augmentation 246

8.1 Increasing Edge-Connectivity by One 247

8.2 Star Augmentation 249

8.3 Augmenting Multigraphs 252

8.4 Augmenting Weighted Graphs 254

8.5 More on Augmentation 276

9 Source Location Problems 282

9.1 Source Location Problem Under Edge-Connectivity Requirements 283

9.2 Source Location Problem Under Vertex-Connectivity Requirements 295

10 Submodular and Posimodular Set Functions 304

10.1 Set Functions 304

10.2 Minimizing Submodular and Posimodular Functions 306

10.3 Extreme Subsets in Submodular and Posimodular Systems 315

10.4 Optimization Problems over Submodular and Posimodular Systems 320

10.5 Extreme Points of Base Polyhedron 336

10.6 Minimum Transversal in Set Systems 342

Bibliography 357

Index 371