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

网络最大流问题典型组合算法研究 被引量：8

Research on the Typical Algorithms for the Maximum-flow Problem of Networks
下载PDF
导出
摘要 简述了网络最大流问题的现状,详细分析了几种具有广泛代表性的网络最大流问题组合算法,同时,阐述了几种在特殊网络结构上的网络最大流问题.对网络最大流问题的深入研究具有重要意义和实用价值. The condition of the maximum flow problem is proposed simply in this article. It introduces in details several typical algorithms for the maximum - flow problem of networks, and presents maximum - flow problem of networks on several networks structure. It has an important significance and useful worthy for further research on the maximum - flow problem of networks.
作者 凌永发 王杰 李正明
机构地区 云南民族大学物理与电子电气信息工程学院 楚雄师范学院
出处 《云南民族大学学报（自然科学版）》 CAS 2006年第3期211-214,共4页 Journal of Yunnan Minzu University:Natural Sciences Edition
基金 云南省计算机应用技术重点实验室开放基金资助项目
关键词 最大流问题 算法 网络结构 maximum flow problem algorithm networks structure
分类号 TP301.06 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献10

  • 1GOLDBERG A V, BEYOND S R. The flow decomposition barrier[J]. J Assoc Compute Mach, 1998, 45(5) : 783 -797.
  • 2张宪超,陈国良,万颖瑜.网络最大流问题研究进展[J].计算机研究与发展,2003,40(9):1281-1292. 被引量：52
  • 3AHUJA R K, MAGNANTI T L. Network Flows: Theory, Algorithms and Applications[M]. New Jersey : Prentice - Hall.2000.
  • 4FORD L R, FULKEPSON D R. Maximum flow through a network[J].Canadian Journal of Math, 1956, 8(5) : 399 -404.
  • 5DINIC 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.
  • 6GOLDBERG A V ,TARJAN R E.A new approach to the maximum flow problem[J]. J Assoc Compute Mach, 1988, 35(4) :921 -940.
  • 7GOLDBERG A V, RAO S. Beyond the flow decomposition barrier[J].J Assoc Compute Mach, 1998, 45(5) : 783 -797.
  • 8GOLDBERG A V, RAO S. Flows in undirected unit capacity networks[J]. SIAM J Discrete Math, 1999, 12(1): 1 -5.
  • 9WEIHE K . Maximum(s,t) -flowsin planar networks in O(｜V｜log｜V｜ ) time[J].J computer and System Sciences, 1997,16(6) : 454 -475.
  • 10AHUJA R K, ORLIN J B, STEIN C, et al.Improved algotithms for bipartite network flow[ J ]. SIAM J Compute, 1994, 23(5) : 906 -933.

二级参考文献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

同被引文献44

  • 1沈金龙,喻锦华.计算机通信网最大流算法的分析和实现[J].南京邮电学院学报,1994,14(4):71-80. 被引量：1
  • 2解季萍,杨超,谢刚.网络最大流问题和典型阻塞流算法研究[J].西南林学院学报,2005,25(2):71-72. 被引量：2
  • 3徐周波,古天龙,赵岭忠.网络最大流问题求解的符号ADD增广路径算法[J].计算机科学,2005,32(10):38-40. 被引量：9
  • 4R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network flows theory, algorithms and applications[M]. New Jersey : Prentice Hall, 1993.
  • 5Z. Galil, A. Naamad. An algorithm for the maximum flow probem[J].J. Comput System Sci., 1980,21(2):203- 217.
  • 6D. D. Sleator, R. E. Tarjan. A data structure for dynamic tree[J].J. Comput System Sci. , 1983,26 (3) :362-391.
  • 7Ford L. R. Jr., Fulkerson D. R. Maximal flow through a network[J]. Cana. J. Math., 1956,8: 111-114.
  • 8甘爱英.运筹学[M].北京:清华大学出版社,2002:254-278.
  • 9焦永兰.管理运筹学[M].北京:中国铁道出版社,2005:145-191.
  • 10AVINDRA R K, THOMAS M L, JAMES O B. Network flows : theory, algorithms, and applications [ M ]. Princeton: Prentice- Hall, 1993 : 46-210.

引证文献8

二级引证文献27

云南民族大学学报（自然科学版）
2006年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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