MAXIMAL FLOW MODEL AND ITS APPLICATIONS
Keywords:
Network, Maximal-Flow Model, Residual network, Source-Sink
Abstract
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.
Downloads
Download data is not yet available.
References
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
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
Published
2019-02-17
How to Cite
Ahmad, M. (2019). MAXIMAL FLOW MODEL AND ITS APPLICATIONS. IJRDO -JOURNAL OF MATHEMATICS, 5(2), 01-15. https://doi.org/10.53555/m.v5i2.2586
Section
Articles
Copyright (c) 2019 IJRDO - Journal of Mathematics (ISSN: 2455-9210)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Author(s) and co-author(s) jointly and severally represent and warrant that the Article is original with the author(s) and does not infringe any copyright or violate any other right of any third parties, and that the Article has not been published elsewhere. Author(s) agree to the terms that the IJRDO Journal will have the full right to remove the published article on any misconduct found in the published article.
