网络流算法

图书标准信息

• 作者 [美]大卫·P. 威廉姆森（David P. Williamson）
• 出版社 机械工业出版社
• 出版时间 2022-03
• 版次 1
• ISBN 9787111701071
• 定价 99.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 240页
• 字数 322千字

【内容简介】

网络流理论在理论计算机科学、运筹学和离散数学等学科中均有应用，可用于货物运输建模和计算机视觉图像分割等众多问题。本书主要源于康奈尔大学的网络流算法课程讲义，包含出版年代较早的经典书籍中未能涵盖的新研究成果。本书采用简洁且统一的视点，讨论解决网络流问题的多种组合算法、多项式算法及其分析，涵盖流、小代价流、广义流、多物流和全局小割集等，还介绍了关于计算电流的新研究成果及其在经典问题上的应用。本书可作为面向研究生的网络流算法教材，也适合该领域的研究人员参考。

【作者简介】

---作者简介---

大卫·P. 威廉姆森（David P. Williamson）  康奈尔大学运筹学和信息工程学院教授，ACM会士，SIAM会士。他在离散优化方面的研究获得了多个奖项，包括2000年由美国数学协会和数学规划协会赞助的Fulkerson奖。他与David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge, 2011）获得了2013年的INFORMS Lanchester奖。他在多个编委会任职，曾任SIAM Journal on Discrete Mathematics的主编。

---译者简介---

吴向军 博士，中山大学副教授。主要研究方向为人工智能和算法设计等，近年来主要从事智能规划领域的研究和规划系统的设计与开发。

【目录】

译者序 

前言 

致谢 

第 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