 When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more. |
The required text is: Ahuja, Magnanti, and Orlin. Network Flows: Theory, Algorithms, and Applications. 1st ed. Upper Saddle River, NJ: Prentice Hall, February 18, 1993. ISBN: 013617549X. "AMO Reading" refers to this text.
| 1 |
Introduction to Network Models |
1-22, 53-63 |
| 2 |
Computational Complexity and Data Structures |
23-38, 765-773 |
| 3 |
Graph Search Algorithms |
38-47, 66-79 |
| 4 |
Transformations and Flow Decomposition |
79-86 |
| 5 |
Shortest Paths: Label Setting Algorithms |
93-114 |
| 6 |
The Radix Heap Algorithm |
115-124 |
| 7 |
Shortest Paths: Label Correcting Algorithms |
133-147, 149-150, 154-157 |
| 8 |
Basic Algorithms for The Maximum Flow Problem |
166-187 |
| 9 |
Combinatorial Applications of Maximum Flows |
188-198 and 207-223 |
| 10 |
Preflow Push Algorithms |
223-237 |
| 11 |
More on Preflow Push Algorithms |
238-242 |
| 12 |
Midterm |
|
| 13 |
The Global Min Cut Algorithm |
Class Handout |
| 14 |
Minimum Cost Flows: Basic Algorithms |
294-319 |
| 15 |
The Successive Shortest Path Algorithm |
320-326 |
| 16 |
The Network Simplex Algorithm |
402-453 |
| 17 |
Minimum Cost Spanning Trees |
510-536 |
| 18 |
Review of Linear Programming |
802-820 |
| 19 |
Generalized Flows |
566-592 |
| 20 |
Lagrangian Relaxation 1 |
598-615 |
| 21 |
Lagrangian Relaxation 2 |
615-638 |
| 22 |
Multicommodity Flows |
649-671 |
| 23 |
Multicommodity Flows |
671-683 |
| 24 |
Very Large Scale Neighborhood Search |
Class Handout |
|