网络最优化中的一个扩容算法被引量：2

导出

摘要指出了网络最小割集与网络瓶颈的关系,提出了解决网络瓶颈问题的一个优化扩容算法,并分析了算法复杂性.算法通过在给出了容量的网络中全局正向分段引入虚拟发点、构造扩容网络搜索全部最小割集;对于指定的网络最大流量,算法反向逐级计算各个最小割集弧组相应的调整量,通过增加调整量来重新布局各弧的容量,逐级回代直至恢复原网络拓扑结构,从而改善网络的通行能力,解决网络瓶颈问题.

作者余胜生刘玉华毛经中许凯华

机构地区华中科技大学计算机科学与技术学院华中师范大学数学系华中师范大学教育信息研究中心

出处《科学通报》 EI CAS CSCD 北大核心 2002年第24期1858-1860,共3页 Chinese Science Bulletin

基金湖北省自然科学基金(批准号:2001ABB013) 湖北省科技攻关重大项目基金(批准号:2001AA105A04)资助项目.

关键词网络最优化最大流最小割集网络瓶颈扩容算法网络拓扑结格网络容量

分类号 O224 [理学—运筹学与控制论]

引文网络
相关文献

参考文献8

1Ahuja R K, Orlin J B, Stein C. Improved algorithms for bipartite network flow. SIAM Journal on Computing, 1994, 23: 906～933
2Ford L R, Fulkerson D R. Maximum flow through a network. Canadian Journal of Math, 1956, 8(5): 399～404
3Goldberg A V, Rao S. Flows in undirected unit capacity networks. SIAM Journal on Discrete Mathematics, 1999, 12: 1～5
4Kolliopoulos S G , Stein C. Approximation algorithms for single- source unsplittable flow. SIAM Journal on Computing, 2002, 31: 919～946
5Ahujia R K, Magnanti T L, Orlin J B. Network Flows: Theory, Algorithms and Applications. Englewood Cliffs: Prentice-Hall, 1993
6Balakrishnam V K. Network Optimization. London: Chapman & Hall, 1995
7张宪超,陈国良.小容量网络上的最大流算法[J].计算机研究与发展,2001,38(2):194-198. 被引量：11
8Cheriyan J, Hagerup T. A randomized maximum-flow algorithm. SIAM Journal on Computing, 1995, 24: 203～226

二级参考文献2

1陈国良,梁维发,沈鸿.并行图论算法研究进展[J].计算机研究与发展,1995,32(9):1-16. 被引量：13
2Goldberg A V，Proc 38th IEEE Annual Symposium on Foundations of Computer Science，1997年，2页

共引文献10

1张凤林,郭波,刘卫华,王正明.有限需求量的网络路径优选研究[J].系统工程,2004,22(11):106-110. 被引量：4
2林志程.Matlab语言在网络最大流中的应用[J].微计算机应用,2005,26(4):466-470.
3况军,李志咏.基于GPS的输电线路智能巡检管理系统的研发[J].电工技术,2006(1):8-10. 被引量：8
4夏林林,叶茂莹,杨凌云,牟廉明.求解最小费用流问题的蚁群算法[J].内江师范学院学报,2010,25(6):30-32. 被引量：6
5赵礼峰,纪亚宝.最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(8):52-54. 被引量：3
6赵礼峰,纪亚劲.基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(8):88-91. 被引量：4
7刘义磊,黄素果.最大流算法在矿井通风系统中的应用[J].科技传播,2012,4(21):174-175.
8张宪超,陈国良,万颖瑜.网络最大流问题研究进展[J].计算机研究与发展,2003,40(9):1281-1292. 被引量：52
9刘玉华,毛经中,肖德宝.一个基于最小割集扩容的网络优化算法[J].计算机科学,2003,30(8):37-39.
10YUShengsheng,LIUYuhua,MAOJingzhong,XUKaihua.Algorithm of capacity expansion on networks optimization[J].Chinese Science Bulletin,2003,48(10):1048-1050.

同被引文献10

1刘舒燕.一种改进的求网络最小截集的算法[J].武汉理工大学学报（交通科学与工程版）,2001,25(2):121-123. 被引量：2
2吴薇薇,宁宣熙.紧急疏散网络防堵塞改造研究[J].系统工程学报,2006,21(3):244-248. 被引量：12
3吴薇薇,宁宣熙.基于改善紧急疏散网络流通能力的仿真研究[J].中国管理科学,2006,14(3):86-91. 被引量：11
4Ahujia R K, Magrmnti T L, Orlin J B. Network Flows : Theory, Algorithms and Applications. Englewood Cliffs, N J: Prentice-Hall, 1993.
5Balakrishnam V K. Network Optimization. London:Chapman & Hall,1995.
6Ford L R, Fulkerson D R. Maximum flow through a network. Canadian Journal of Math,1956,8(5): 399-404.
7Cheriyan J, Hagerup T. A Randomized Maximum-Flow Algorithm. SIAM Journal on Computing,1995,24:203-226.
8Goldberg A V,Rao S. Flows in Undirected Unit Capacity Networks. SIAM Journal on Discrete Mathematies,1999,12:1-5.
9龙小强,谭云龙.基于模糊综合评价的城市道路交通拥堵评价研究[J].交通标准化,2011,39(11):114-117. 被引量：18
10张宪超,陈国良.小容量网络上的最大流算法[J].计算机研究与发展,2001,38(2):194-198. 被引量：11

引证文献2

1侯志伟,申涵瑞,谢强,张杰.深圳关内外交通拥堵探究与治理[J].数学建模及其应用,2013,2(Z1):14-22. 被引量：2
2刘玉华,毛经中,肖德宝.一个基于最小割集扩容的网络优化算法[J].计算机科学,2003,30(8):37-39.

二级引证文献2

1刘耕.最大容量路的扩张问题研究[J].物流技术,2020,39(7):94-96. 被引量：1
2罗甜甜,赵礼峰.基于重置顶点下标的网络最大流算法[J].计算机技术与发展,2020,30(10):26-30. 被引量：1

1Huber＋Suhner推出高精度测试电缆[J].中国电子商情（通信市场）,2005(11M):73-73.
2严冬雪,王攀.“小冰”突击[J].财经天下,2014(14):76-83.
3刘东.IPv6重新布局[J].互联网周刊,2004(10):56-57.
4Huber＋Suhner推出高精度SUCOTEST-18A测试电缆[J].世界仪表与自动化,2006,10(1):8-8.
5刘凯,张立民,孙永威.基于遗传算法的RBM优化设计[J].微电子学与计算机,2015,32(6):96-100. 被引量：7
6邬学军,孟利民,华惊宇,周明华,周凯.基于能量控制的无线传感网络最优化算法研究[J].传感技术学报,2011,24(3):436-439. 被引量：9
7Huber＋Suhner推出高精度SUCOTEST-18A测试电缆[J].电子元器件应用,2005,7(12):139-139.
8长春图商网络有限公司[J].吉林农业,2010(11).
9马宇斌,谢政,陈挚.一种求解最小双费用流问题的算法[J].计算机工程与科学,2014,36(3):446-451. 被引量：1
10马晓华.多层IP骨干网的优势及案例分析[J].电信技术,2006(7):57-60.

科学通报

2002年第24期

浏览历史

内容加载中请稍等...

网络最优化中的一个扩容算法被引量：2

参考文献8

二级参考文献2

共引文献10

同被引文献10

引证文献2

二级引证文献2

相关作者

相关机构

相关主题

浏览历史

网络最优化中的一个扩容算法 被引量：2

参考文献8

二级参考文献2

共引文献10

同被引文献10

引证文献2

二级引证文献2

相关作者

相关机构

相关主题

浏览历史

网络最优化中的一个扩容算法被引量：2