Volume 31, Issue 4, January 2021, Pages 703–711
Dilruba Akter1, Md. Sharif Uddin2, and Faria Ahmed Shami3
1 Department of Applied Mathematics, Gono Bishwabidyalay, Savar, Dhaka, Bangladesh
2 Department of Mathematics, Jahangirnagar University, Savar, Dhaka, Bangladesh
3 Department of Mathematics, Bangabandhu Sheikh Mujibur Rahman Science and Technology University, Gopalganj, Bangladesh
Original language: English
Copyright © 2021 ISSR Journals. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network in much more optimized approach. Edmonds-Karp is identical to Ford-Fulkerson except for one very important trait that is the search order of augmenting paths is well defined. This paper presents some modifications of Edmonds-Karp algorithm for solving maximum flow problem (MFP). Solution of MFP has also been illustrated by using the proposed algorithm to discuss the functionality of proposed method.
Author Keywords: Maximum Flow Problem, Breadth First Search, Augmenting Path, Residual Network, Edmonds-Karp algorithm.
Dilruba Akter1, Md. Sharif Uddin2, and Faria Ahmed Shami3
1 Department of Applied Mathematics, Gono Bishwabidyalay, Savar, Dhaka, Bangladesh
2 Department of Mathematics, Jahangirnagar University, Savar, Dhaka, Bangladesh
3 Department of Mathematics, Bangabandhu Sheikh Mujibur Rahman Science and Technology University, Gopalganj, Bangladesh
Original language: English
Copyright © 2021 ISSR Journals. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network in much more optimized approach. Edmonds-Karp is identical to Ford-Fulkerson except for one very important trait that is the search order of augmenting paths is well defined. This paper presents some modifications of Edmonds-Karp algorithm for solving maximum flow problem (MFP). Solution of MFP has also been illustrated by using the proposed algorithm to discuss the functionality of proposed method.
Author Keywords: Maximum Flow Problem, Breadth First Search, Augmenting Path, Residual Network, Edmonds-Karp algorithm.
How to Cite this Article
Dilruba Akter, Md. Sharif Uddin, and Faria Ahmed Shami, “Modification of EDMONDS-KARP Algorithm for Solving Maximum Flow Problem,” International Journal of Innovation and Applied Studies, vol. 31, no. 4, pp. 703–711, January 2021.
