Maximum Flow Problem (MFP) discusses the maximum amount of flow that can be sent from the source to sink. Edmonds-Karp algorithm is the modified version of Ford-Fulkerson algorithm to solve the MFP. This paper presents some modifications of Edmonds-Karp algorithm for solving MFP. Solution of MFP has also been illustrated by using the proposed algorithm to justify the usefulness of proposed method.
References
[1]
Ford Jr., L.R. and Fulkerson D.R. (1962) Flows in Networks. Princeton University Press, Princetion, NJ.
[2]
Ford, Jr. L.R. and Fulkerson D.R. (1956) Maximal Flow through a Network. Canadian Journal of Mathematics, 8, 399-404. http://dx.doi.org/10.4153/CJM-1956-045-5
[3]
Edmonds, J. and Karp, R.M. (1972) Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the Association for Computing Machinery, 19, 248-264. http://dx.doi.org/10.1145/321694.321699
[4]
Goldberg, A.V., Tardos, E. and Tarjan, R.E. (1990) Network Flow Algorithms. In: Korte, B., Lovasz, L., Promel, H.J. and Schriver, A., Eds., Paths, Flows, and VLSI-Layout, Vol. 9, Springer-Verlag, Berlin Heidelberg, 101-164.
[5]
Goldberg, A.V. and Tarjan, R.E. (1988) A New Approach to the Maximum-Flow Problem. Journal of the Association for Computing Machinery, 35, 921-940. http://dx.doi.org/10.1145/48014.61051
[6]
Goldberg, A.V., Plotkin, S.A. and Tardos, E. (1991) Combinatorial Algorithms for the Generalized Circulation Problem. Mathematics of Operations Research, 16, 351-381. http://dx.doi.org/10.1287/moor.16.2.351
[7]
Goldberg, E. and Rao, S. (1998) Beyond the Flow Decomposition Barrier. Journal of the ACM, 45, 783-797.
http://dx.doi.org/10.1145/290179.290181
[8]
Cherkasky, B.V. (1977) An Algorithm for Constructing Maximal Flows in Networks with Complexity of Operations. Mathematical Methods of Solution of Economical Problems, 7, 117-125. (In Russian)
[9]
Jain, C. and Garg, D. (2012) Improved Edmond Karps Algorithm for Network Flow Problem. International Journal of Computer Applications, 37, 48-53. http://dx.doi.org/10.5120/4576-6624
[10]
Kelly, D. and O`Neill, G.M. (1991) The Minimum Cost Flow Problem and The Network Simplex Solution Method. Master of Management Science Dissertation, University College Dublin.
[11]
Dinic, E.A. (1970) Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Math Doklady, 11, 1277-1280. http://www.citeulike.org/user/Fujisaki/author/Dinic:EA
[12]
Goldfarb, D. and Jin, Z.Y. (1996) A Faster Combinatorial Algorithm for the Generalized Circulation Problem. Mathematics of Operations Research, 21, 529-539. http://dx.doi.org/10.1287/moor.21.3.529
[13]
Goldfarb, D., Jin, Z.Y. and Orlin, J.B. (1997) Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem. Mathematics of Operations Research, 22, 793-802.
http://dx.doi.org/10.1287/moor.22.4.793
[14]
Hamdy, A.T. (2007) Operations Research: An Introduction. 8th Edition, Pearson Prentice Hall, Upper Saddle River, New Jersey.
[15]
Mallick, J.B. (2014) An Efficient Network Flow Approach: On Development of New Idea & A Modification of EDMONDS-KARP Algorithm. M. Phil. Thesis, Department of Mathematics, Jahangirnagar University.
[16]
Galil, Z. and Naamad, A. (1980) An Algorithm for the Maximal Flow Problem. Journal of Computer and System Sciences, 21, 203-217. http://dx.doi.org/10.1016/0022-0000(80)90035-5
[17]
Ahmed, F., Khan, Md.A., Khan, A.R., Ahmed, S.S. and Uddin, Md.S. (2014) An Efficient Algorithm for Finding Maximum Flow in a Network-Flow. Journal of Physical Sciences, 19, 41-50.
[18]
Khan, Md.A., Rashid, A., Khan, A.R. and Uddin, Md.S. (2013) An Innovative Approach for Solving Maximal-Flow Problems. Journal of Physical Sciences, 17, 143-154.
