CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Improved Edmond Karps Algorithm for Network Flow Problem

by Chintan Jain, Deepak Garg
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 37 - Number 1
Year of Publication: 2012
Authors: Chintan Jain, Deepak Garg
10.5120/4576-6624

Chintan Jain, Deepak Garg . Improved Edmond Karps Algorithm for Network Flow Problem. International Journal of Computer Applications. 37, 1 ( January 2012), 48-53. DOI=10.5120/4576-6624

@article{ 10.5120/4576-6624,
author = { Chintan Jain, Deepak Garg },
title = { Improved Edmond Karps Algorithm for Network Flow Problem },
journal = { International Journal of Computer Applications },
issue_date = { January 2012 },
volume = { 37 },
number = { 1 },
month = { January },
year = { 2012 },
issn = { 0975-8887 },
pages = { 48-53 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume37/number1/4576-6624/ },
doi = { 10.5120/4576-6624 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:23:13.546944+05:30
%A Chintan Jain
%A Deepak Garg
%T Improved Edmond Karps Algorithm for Network Flow Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 37
%N 1
%P 48-53
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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
  3. Bazarra, M. and J. Jarvis. Linear Programming and Network Flows. John Wiley & Sons, 1977.
  4. Ford, L. R. Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
  5. “Maximum Flow Problem” http://en.wikipedia.org/wiki/Maximum_flow_problem
  6. “Recent Developments in Maximum Flow Algorithms” www.springerlink.com/index/tfdyr7n9xyer80p7.pdf
  7. Ravindra K. Ahuja and James B. Orlin. “A fast and simple algorithm for the maximum flow problem”. Operations Research, 37(5):748–759, 1989.
  8. 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.
  9. “Network Flow Programming” www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf.
  10. Mircea Parpalea. Min-Max Algorithm For ThParametric Flow Problem Bulletin of the Transilvania University of Bra¸sov , Vol 3(52) , 2010
  11. Dorit S. Hochbaum. The Pseudoflow algorithm: A New Algorithm for the Maximum Flow Problem, Operations research, 2008
Index Terms

Computer Science
Information Sciences

Keywords

Edmonds-Karp algorithm Maximum flow problem Residual graph Ford-Fulkerson method

Powered by PhDFocusTM