• Mobin Ahmad Jazan University
Keywords: Network, Maximal-Flow Model, Residual network, Source-Sink


Most extreme stream issue. In the conventional most extreme stream issue, there is a capacitated arrange and the objective is to send however much of a solitary item as could be expected between two recognized hubs, without surpassing the circular segment limit limits. The issue has many applications including: shipping cargo in transportation arrange and directing liquid through a pressure driven system.


Download data is not yet available.

Author Biography

Mobin Ahmad, Jazan University

Department of Mathematics, Faculty of Science, Jazan University, Jazan 45142, Saudi Arabia


1. Cunningham, W.H. (1976): A network simplex method. Math. Program. //, 105-116
2. Goldfarb, D., Hao, J. (1988): A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and 0(t?m) time. Technical Report, Department of Industrial Engineering and Operations Research, Columbia University
3. Grigoriadis, M.D. (1986): An efficient implementation of the network simplex method. Math. Program. Study 26, 83-111
4. Orlin, J.B. (1984): Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. Technical Report No. 1615-84, Sloan School of Management, M.I.T.
5. Ford jr., L.R., Fulkerson, D.R. (1962): Flows in networks. Princeton University Press, Princeton, NJ
6. Ford jr., L.R., Fulkerson, D.R. (1956): Maximal flow through a network. Can. J. Math. 8, 399^104
7. Goldberg, A.V. (1985): A new max-flow algorithm. Technical Report MIT/LCS/ TM-291, Laboratory for Computer Science, M.I.T.
8. Dinic, E.A. (1970): Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277-1280
9. Edmonds, J., Karp, R.M. (1972): Theoretical improvements in algorithmic efficiency for network flow problems. J. Assoc. Comput. Mach. 19, 248-264
10. Goldberg, A.V., Tarjan, R.E. (1986): A new approach to the maximum flow problem. Proc. 18th ACM STOC, pp. 136-146
11. Fulkerson, D.R. (1961): An out-of-Kilter method for minimal cost flow problems. SIAM J. Appl. Math. 9, 18-27
12. Minty, G.J. (1960): Monotone networks. Proc. R. Soc. Lend., Ser. A 257, 194-212
13. [105] Yakovleva, M.A. (1959): A problem on minimum transportation cost. In: Nemchinov, V.S. (ed.): Applications of mathematics in economic research. Izdat. Social'noEkon. Lit., Moscow, pp. 390-399
14. Renegar, J. (1988): A polynomial time algorithm, based on Newton's method, for linear programming. Math. Program. 40, 59-94
15. Tardos, E. (1985): A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247-255
16. Jewell, W.S. (1962): Optimal flow through networks with gains. Oper. Res. 70, 476-499
17. Truemper, K. (1977): On max flows with gains and pure min-cost flows. SIAM J. Appl. Math. 32, 450-456
18. [70] Khachiyan, L.G. (1980): P
19. Kapoor, S., Vaidya, P.M. (1986): Fast algorithms for convex quadratic programming and multicommodity flows. Proc. 18th ACM STOC, pp. 147-159
20. Karmarkar, N. (1984): A new polynomial-time algorithm for linear programming. Combinatorica 4, 373-395
21. Goldberg, A.V., Plotkin, S.A., Tardos, E. (1988): Combinatorial algorithms for the generalized circulation problem Technical Report STAN-CS-88-1209, Stanford University (Also available as Technical Memorandum MIT/LCS/TM-358, Laboratory for Computer Science, M.I.T.)
22. Konig, D. (1950): Theorie der endlichen und unendlichenGraphen. Chelsea Publishing Co., New York, NY
23. Hopcroft, J.E., Karp, R.M. (1973): An n i/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput. 2, 225-231
24. Even, S., Tarjan, R.E. (1975): Network flow and testing graph connectivity. SIAM J. Comput. 4, 507-518
25. Kuhn, H.W. (1955): The Hungarian method for the assignment problem. Nav. Res. Logist. 2, 83-97
26. Orlin, J.B., Ahuja, R.K. (1987): New distance-directed algorithms for maximumflow and parametric maximum-flow problems. Sloan Working Paper 1908-87, Sloan School of Management, M.I.T
27. Gabow, H.N. (1985): Scaling algorithms for network problems. J. Comput. Syst. Sci. 31, 148-168
28. Tomizawa, N. (1972): On some techniques useful for solution of transportation networks problems. Networks 1, 173-194
29. [106] Zadeh, N. (1973): A bad network problem for the simplex method and other minimum cost flow problems. Math. Program. 5, 255-266
30 Fredrickson, G. (1987): Fast algorithms for shortest paths in planar graphs with applications. SIAM J. Comput. 16, 1004-1022
32 Fujishige, S. (1986): A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm. Math.Program. 35, 298-308
33. Fulkerson, D.R. (1961): An out-of-Kilter method for minimal cost flow problems. SIAM J. Appl. Math. 9, 18-27
34. Gabow, H.N., Tarjan, R.E. (1988): Almost-optimal speed-ups of algorithms for matching and related problems. Proc. 20th ACM STOC, pp. 514-527
35. Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput., to appear