Edmonds–Karp algorithm: Difference between revisions

Revision as of 03:16, 16 November 2005

Revision as of 09:31, 16 November 2005

Line 3:

The Edmonds-Karp algorithm runs in [[Big O notation|O]](VE²) time, where V is the number of vertices and E is the number of edges in the network.

The algorithm was first discoveredpublished by a Russian scientist, DinitsDinic, in 1970, and later, independently, by Edmonds and Karp who published it in the 1972. paper "TheoreticalDinic' Improvementsalgorithm inincludes Algorithmicadditional Efficiencytechniques forthat Network Flow Problems," by [[Jack Edmonds]] and [[Richard Karp]], inreduce the ''Journalrunning oftime the [[Association for Computing Machinery|ACM]]''. Dinits actually proved a tighter bound on the algorithm,to [[Big O notation|O]](EV²).

==External linkReferences==

* E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, ''Soviet Math. Doklady'', Vol 11 (1970) pp1277-1280.

[http://delivery.acm.org/10.1145/330000/321699/p248-edmonds.pdf The 1972 paper in PDF format, at the ''JACM'' Web site] (needs subscription)

* J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for networkl flow problems, ''Journal of the [[Association for Computing Machinery|ACM]]'', Vol 19, No. 2 (1972) pp248-264. [http://delivery.acm.org/10.1145/330000/321699/p248-edmonds.pdf PDF (needs subscription)]

{{compu-stub}}

[[Category:Graph algorithms]]