This unit is about Network Flow (or Maximum Flow), Minimum Cut, and how to model a variety of problems as a max flow on a graph. The theory covered is:
- Max flow and its "augmenting path" solution (Edmonds-Karp)
- Minimum cut
- Maximum Cardinality Bipartite Matching (move to unit 22?)
- Min Path Cover on DAG (move to unit 22?)
- Maximum edge/node-disjoint paths
- Minimum Cost Max Flow
- Unit 14: Graph traversal
- Unit 17: Single-source shortest path (for min cost max flow)
- UVa 820 - Internet Bandwidth
- UVa 12125 - March of the Penguins
- UVa 10092 - The Problem with the Problem Setter
- UVa 563 - Crimewave
- UVa 11757 - Winger Trial