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

• 作者: 华波 张燕平 许显胜 赵姝
• 来源期刊: 模式识别与人工智能
• 学科: 工学
• 关键词: 最大流 收缩邻居节点集方法 有向网络
• 年，卷（期）: 2013,（5）
• 页码范围: 425-431
• 页数: 7页
• 分类号: TP301.6|TP393
• 字数: 5475字
• 语种: 中文

摘要

@@@@最大流问题在许多领域有广泛的应用，然而随着网络规模的增加，传统的算法无法快速高效地求解最大流问题。对一个给定的有向网络，文中提出一种收缩邻居节点集的方法(CNA)求解其最大流。该方法通过收缩邻居节点集有效降低网络规模，使经典算法及改进算法可直接使用。首先给出收缩邻居节点集的条件，接着给出依据收缩条件构建目标网络的算法，最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似。实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半，且能以较小的误差求得初始网络的最大流。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张燕平	安徽大学计算机科学与技术学院	148	1556	21.0	32.0
5	赵姝	安徽大学计算机科学与技术学院	82	555	13.0	19.0
9	许显胜	安徽大学计算机科学与技术学院	1	2	1.0	1.0
13	华波	安徽大学计算机科学与技术学院	1	2	1.0	1.0