网络最大流的自适应求解算法——SAPR算法

• 作者: 吴立新 李志锋 杨宜舟 江锦成
• 来源期刊: 计算机应用研究
• 关键词: 最大流 自适应 预流推进 网络分析 H_PRF算法 动态
• 年，卷（期）: 2014,（10）
• 页码范围: 2969-2973
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.10.020

摘要

为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法.在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法.SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴立新	中国矿业大学物联网中心	48	1207	19.0	34.0
5	杨宜舟	东北大学测绘遥感与数字矿山研究所	12	103	6.0	10.0