摘要
NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法。该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率。通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络。
The NW（ Newman-Watts） small-world network and the BA（ Barabasi-Albert） scale-free network are two kinds of common network in reality, these two kinds of networks have a highly possibility existing multiple paths between any pair of vertexes. If abandoning saturated augmented chain and finding augmented chain, the efficiency is not high. The fact above urged a high performance new algorithm described as minimum cut / maximum flow algorithm based on augmenting path restoration to manage these two networks. The new algorithm constantly sought vertexes following greedy heuristics to restore saturated augmenting paths which generated by adjusting flow on shortest paths. By experimental comparisons on the NW small-world network and the BA scale-free network, the new algorithm was several times faster than Ford-Fulkerson algorithm and half as Dinic algorithm in RAM usage, as a consequence, the new algorithm was capable of calculating growing telecommunication and traffic networks.
出处
《计算机应用》
CSCD
北大核心
2015年第5期1246-1249,共4页
journal of Computer Applications
关键词
最大流
增广链
增广链修复
NW小世界网络
BA无标度网络
maximum flow
augmenting path
augmenting path restoration
NW small-world network
BA scale-free network
