Improved Edmond Karps Algorithm for Network Flow Problem
|
10.5120/4576-6624 |
Chintan Jain and Deepak Garg. Article: Improved Edmond Karps Algorithm for Network Flow Problem. International Journal of Computer Applications 37(1):48-53, January 2012. Full text available. BibTeX
@article{key:article,
author = {Chintan Jain and Deepak Garg},
title = {Article: Improved Edmond Karps Algorithm for Network Flow Problem},
journal = {International Journal of Computer Applications},
year = {2012},
volume = {37},
number = {1},
pages = {48-53},
month = {January},
note = {Full text available}
}
Abstract
Network Flow Problems have always been among the best studied combinatorial optimization problems. Flow networks are very useful to model real world problems like, current flowing through electrical networks, commodity flowing through pipes and so on. Maximum flow problem is the classical network flow problem. In this problem, the maximum flow which can be moved from the source to the sink is calculated without exceeding the maximum capacity. Once, the maximum flow problem is solved it can be used to solve other network flow problems also. The FORD-FULKERSON algorithm is the general algorithm which can solve all the network flow problems. The improvement of the Ford Fulkerson algorithm is Edmonds-Karp algorithm which uses BFS procedure instead of DFS to find an augmenting path. The modified Edmonds-Karp algorithm is designed to solve the maximum flow problem in efficient manner.
References
- Andrew V. Goldberg, Eva Tardos and Robert E. Tarjan (1988). A new approach to the maximum-flow problem. Journal of the ACM. 35:921–940
- Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. doi:10.1145/321694.321699
- Bazarra, M. and J. Jarvis. Linear Programming and Network Flows. John Wiley & Sons, 1977.
- Ford, L. R. Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
- “Maximum Flow Problem” http://en.wikipedia.org/wiki/Maximum_flow_problem
- “Recent Developments in Maximum Flow Algorithms” www.springerlink.com/index/tfdyr7n9xyer80p7.pdf
- Ravindra K. Ahuja and James B. Orlin. “A fast and simple algorithm for the maximum flow problem”. Operations Research, 37(5):748–759, 1989.
- Ravindra K. Ahuja, James B. Orlin, and Robert E. Tarjan. “Improved time bounds for the maximum flow problem”. SIAM Journal on Computing, 18(5):939–954, 1989.
- “Network Flow Programming” www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf.
- Mircea Parpalea. Min-Max Algorithm For ThParametric Flow Problem Bulletin of the Transilvania University of Bra¸sov , Vol 3(52) , 2010
- Dorit S. Hochbaum. The Pseudoflow algorithm: A New Algorithm for the Maximum Flow Problem, Operations research, 2008