IE 411: Graphs and Network Flows (C++ and GIDEN)
Miscellaneous Handouts and Course Information
Lecture Slides
- Introduction
- Lecture 1: Paths, Trees, and Cycles
- Lecture 2: Network Data Structures
- Lecture 3: Computational Complexity
- Lecture 4: Search Algorithms
- Lecture 5: Shortest Path Problem
- Lecture 6: Dijkstra’s Algorithm
- Lecture 7: General Label-Correcting Algorithms
- Lecture 8: All-Pairs Shortest Path Algorithms
- Lecture 9: The Maximum Flow Problem
- Lecture 10: Augmenting Path Algorithm
- Lecture 11: Shortest Augmenting Path Algorithm
- Lecture 12: Preflow-push Algorithm
- Quiz 1 Review
- Lecture 13: Minimum Cost Flow Problem
- Lecture 14: Primal-Dual Algorithms
- Lecture 15: Spanning Tree Solutions
- Lecture 16: Network Simplex Algorithm
- Lecture 17: Sensitivity Analysis
- Lecture 18: Minimum Spanning Trees
- Lecture 19: Matroids and Matching
- Lecture 20: Lagrangian Relaxation
- Lecture 21: Multicommodity Flow Problems
- Lecture 22: Final Review
Assignments
Reference Texts
- Course Text: Network Flows by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.
On-line Reference
- Similar course at Berkeley with good pointers to additional material.
Course Software
If you find something here useful, buy me a beer!
