MA015 Graph Algorithms
Lecture II - Maximum Flows (in networks)
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
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/1433/podzim2015/MA015/um/02-flows.pdf