- 作 者：
- 出 版 社：CAMBRIDGE UNIVERSITY PRESS
- 出版年份：2008
- ISBN：9780521878647
- 标注页数：375 页
- PDF页数：390 页
请阅读订购服务说明与试读!
订购服务说明
1、本站所有的书默认都是PDF格式，该格式图书只能阅读和打印，不能再次编辑。
2、除分上下册或者多册的情况下，一般PDF页数一定要大于标注页数才建议下单购买。【本资源390 ≥375页】
图书下载及付费说明
1、所有的电子图书为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、电子图书在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
3、所有的电子图书都是原书直接扫描方式制作而成。
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