收缩邻居节点集方法(CNA)求解有向网络的最大流问题

摘要：

最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应用.然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题,算法的实际性能也不能满足许多应用问题的要求.针对求解一个给定的有向网络上最大流问题,本文提出一种新方法——收缩邻居节点集的方法(CNA).该方法旨在通过收缩邻居节点集来有效降低网络规模,使得经典算法及改进算法可以直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明收缩邻居节点集的方法不仅平均能将目标网络的规模降至初始网络的一半,而且能够以非常小的误差求得初始网络的最大流.

关键词： Maximum flow Contraction Contracting neighbor-node-set approach (CNA) Directed network

作者: 赵姝 许显胜 华波 张燕平

作者单位: 安徽大学计算机科学与技术学院 合肥230039 安徽大学计算智能与信号处理教育部重点实验室 合肥230039

会议类型: 国内会议

会议名称: 第十二届中国Rough集与软计算学术会议、第六届中国Web智能学术研讨会及第六届中国粒计算学术研讨会联合学术会议

会议地点: 合肥

会议语种:中文

页码: 34-34

在线出版日期: 2012-10-13（万方平台首次上网日期，不代表论文的发表时间）