基于增广链修复的最大流求解算法

赵礼峰; 严子恒

首页> 中文期刊> 《计算机应用》 >基于增广链修复的最大流求解算法

基于增广链修复的最大流求解算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.

著录项

来源
《计算机应用》 |2015年第5期|1246-1249|共4页
作者
赵礼峰; 严子恒;
展开▼
作者单位

南京邮电大学理学院;

南京210000;

南京邮电大学理学院;

南京210000;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
最大流; 增广链; 增广链修复; NW小世界网络; BA无标度网络;

相似文献

中文文献
外文文献
专利

1. 基于连续最短增广链的网络最大流分析 [J] . 李港1 ,苗金宝1 ,胡春安1 . 计算机科学与应用 . 2018,第010期
2. 基于最短增广链的最大流改进算法 [J] . 赵礼峰 ,纪亚劲 . 计算机技术与发展 . 2017,第008期
3. 最大流问题的最短增广链改进算法 [J] . 邵丽萍 ,赵礼峰 . 计算机技术与发展 . 2019,第005期
4. 最大流问题的改进最短增广链算法 [J] . 赵礼峰 ,纪亚宝 . 计算机技术与发展 . 2016,第008期
5. 求解最大流问题的增广链算法 [J] . 支天红 . 林区教学 . 2012,第002期
6. 供应链网络中最大流问题的计算方法 [C] . 张彤 . OA'2001办公自动化国际学术研讨会 . 2001
7. 基于顶点的网络最大流求解算法 [A] . 罗甜甜 . 2020

基于增广链修复的最大流求解算法

摘要

著录项

相似文献

相关主题

期刊订阅