网络流算法

定　价：¥99.00

作　者：	[美]大卫·P. 威廉姆森(David P. Williamson)
出版社：	机械工业出版社
丛编项：
标　签：	暂缺

购买这本书可以去

ISBN：	9787111701071	出版时间：	2022-03-01	包装：	平装-胶订
开本：	16开	页数：		字数：

内容简介

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

作者简介

　　：作者简介：大卫·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