Dates

13.10. (Ford-Fulkerson [revision], Edmonds-Karp, Dinic [part])

24.10. (finished Dinic, MPM [Three Indians], Dinic with unit/integral capacities)

Reading

D. Kozen: The Design and Analysis of Algorithms. [Chapters 16-18] [PDF]

Contains Edmonds-Karp, Dinic, MPM (Three Indians)

S. Even, R. E. Tarjan (1975). "Network Flows and Testing Graph Connectivity". SIAM Journal on Computing 4 (4): 507-518. doi:10.1137/0204043 [PDF]

Read this for Dinic's algorithm with unit capacities.

Goldberg, Tarjan: Efficient Maximum Flow Algorithms. Communications of the ACM 57 (8) doi:10.1145/2628036

Very nice recent overview of the current state of the maximum flow algorithms. 

Historical references

• Yefim Dinitz (2006). Dinitz' Algorithm: The Original Version and Even's Version
• Harris, Ross (1955). Fundamentals of a Method for Evaluating Rail Net Capacities
• Ford, Fulkerson (1956). "Maximal flow through a network". Canadian Journal of Mathematics 8: 399. doi:10.4153/CJM-1956-045-5.
• Edmonds, Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems".Journal of the ACM  19 (2): 248–264. doi:10.1145/321694.321699.

Slides