期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

级连层次图的网络最大流算法研究

Research on network maximum flows algorithm of cascade level graph
下载PDF
导出
摘要 给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=(G,s,t,C),该算法可在O(n2)时间内快速求出流经网络N的最大网络流及达最大流时的网络流。 This paper gives an algoritm that structures a network cascade level graph to find out maximum flow of the network indirectly.For the given network N=（G,s,t,C） that has n vetexes and e arcs,this algorithm finds out the maximum value of the network flow fast in O（n2） time that flows from the network N and the network flows when the value of the one reach maximum.
作者 潘荷新 伊崇信 李满
机构地区 常州纺织服装职业技术学院信息技术系 山东华宇职业技术学院计算机系
出处 《计算机工程与应用》 CSCD 北大核心 2011年第19期78-81,135,共5页 Computer Engineering and Applications
关键词 网络 级连层次图 最大流 network cascade level graph maximum flow
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献8

  • 1Minieks E.Optimization algoritm for networks and graphs[M]. NY:Marcel Dekker, 1978.
  • 2Dinic E A.Algorithm for solution of a problem of maximum flow in networks with power estimation[J].Soviet Math Dokl, 1970,11 (8) : 1277-1280.
  • 3张宪超,陈国良,万颖瑜.网络最大流问题研究进展[J].计算机研究与发展,2003,40(9):1281-1292. 被引量：52
  • 4Karzanov A V.Determining maximum flow in a network by the method of preflows[J].Soviet Math Dokl, 1974,15(3) :434-437.
  • 5周培德.算法设计与分析[M].北京:机械工业出版社,1998:161-176.
  • 6Aho A V,Hopcroft J E,Uiiman J D.The design and analisis of computer algorithms[M].MA:Addison-Wesley Reading, 1974. Sleator D D.An O(nxmxlbn) algorithm for maximum network flow[D].Standard University, 1980.
  • 7李维铮.运算学[M].北京:清华大学出版社,1985:302-313.
  • 8Edimonds J, Karp R M.Theoretical improvement, in algorithmic effeciency for networkers flow problems[J].J Assoc Comput Math, 1972,19(2) :248-264.

二级参考文献126

  • 1R K Ahuja, J B Orlin. A fast and simple algorithm for the maximum flow problem. Oper Res, 1989, 37(5) : 748～759.
  • 2R K Ahuja, J B Orlin, R E Tarjan. Improved time bounds for the maximum flow problem. SIAM J Computing, 1989, 18(5): 939-954.
  • 3N Alon. Generating pseudo-random permutations and maximum flow algorithms. Information Processing Letters, 1990, 35 ( 4 ) :201-203.
  • 4V King, S Rao, R Tarjan. A faster deterministic maximum flow algorithm. J Algorithms, 1994, 17(3): 447～474.
  • 5J Cheriyan, T Hagerup, K Mehlhom. An O( n^3)-time maximum flow algorithm. SIAMJ Computing, 1996, 25(6): 1144～1170.
  • 6H N Gabow. Scaling algorithms for network problems. J Comput System Sci, 1985, 31(2): 148-168.
  • 7R K Ahuja, J B Orlin. Distance-directed augmenting path algorithms for the maximum flow problem. Naval Research Logisties Quarterlv. 1991. 38(2): 413～430.
  • 8V M Malhotra, M P Kumar, S N Mahesh-wari. An O ( | V^3| )algorithm for finding maximum flows in networks. Information Processing Letters, 1978, 7(6) : 277～278.
  • 9A V Goldberg, R E Tarjan. Finding minimum-cost circulations by successive approximation. Math Oper Res, 1990, 15(3): 430～466.
  • 10D Hochbuam. The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. In: R E Bixby, E A Boyd, Roger et al eds. Proc of the Integer Programming and Combinatorial Optimization 6th Int' l Conf ( LNCS 1412 ) .Heidelberg: Springer-Verlag, 1998. 325～337.

共引文献51

计算机工程与应用
2011年 第19期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部