网络流算法

译者序
前言
致谢
第 1 章 预备知识：*短路径算法 1
1.1 无负权边：Dijkstra 算法 2
1.2 有负权边：Bellman-Ford算法 5
1.3 负权回路的检测算法 9
练习 16
章节后记 17
第 2 章 *大流算法 19
2.1 *优化条件 21
2.2 应用：汽车共享问题 27
2.3 应用：棒球队淘汰问题 28
2.4 应用：*密子图问题 33
2.5 *大改进增广路径算法 37
2.6 容量度量算法 40
2.7 *短增广路径算法 42
2.8 推送–重标算法 44
练习 54
章节后记 59
第 3 章 全局*小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 随机合并算法 72
3.4 Gomory-Hu 树 76
练习 83
章节后记 85
第 4 章 其他*大流算法 88
4.1 阻塞流算法 88
4.2 单位容量图的阻塞流 90
4.3 Goldberg-Rao 算法 92
练习 96
章节后记 97
版权声明 97
第 5 章 *小代价环流算法 99
5.1 *优化条件 101
5.2 Wallacher 算法 104
5.3 *小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 网络单纯形 124
5.7 应用: 带时限的*大流问题 126
练习 130
章节后记 136
第 6 章 广义流算法 139
6.1 *优化条件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 负代价 GAP 检测 151
6.4 有损图、Truemper 算法和收益度量 155
6.5 误差度量 161
练习 163
章节后记 164
第 7 章 多物流算法 166
7.1 *优化条件 166
7.2 双物流问题 168
7.3 预备知识：乘权算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
练习 184
章节后记 185
第 8 章 电流算法 187
8.1 *优化条件 187
8.2 无向图的*大流问题 196
8.3 图的稀疏化 199
8.4 简易 Laplacian 求解器 204
练习 210
章节后记 212
版权声明 213
第 9 章 开放问题 214
参考文献 216