Algorithmic Aspects of Graph Connectivitypdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

Algorithmic Aspects of Graph ConnectivityPDF格式电子书版下载

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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