动态网络中最大流快速增量求解

• 作者: 吕建华 张柏礼 洪亮 王媛瑗 田伟
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 最大流 增量算法 增广路径选择树 简单路径
• 年，卷（期）: 2017,（3）
• 页码范围: 450-455
• 页数: 6页
• 分类号: TP301.6|TP393
• 字数: 4778字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2017.03.006

摘要

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA_ ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA_ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张柏礼	东南大学计算机科学与工程学院	32	326	9.0	17.0
5	吕建华	东南大学计算机科学与工程学院	20	141	7.0	11.0
9	田伟		7	71	6.0	7.0
10	洪亮		3	8	1.0	2.0
11	王媛瑗	东南大学计算机科学与工程学院	1	8	1.0	1.0