Steps

Input & Output
High level description: base case + induction
Complexity: how much each step cost + how many steps
Proof: base case + induction

Famous Problems

Steps

Constraints: restate question requirements
Formulation: (1) draw flow graph, (2) nodes, (3) edges, (4) capacities
Solution: the requirement for the max-flow
Complexity/Algorithm: what algorithm is used + the corresponding complexity
Correctness: restate the formulation with the implications

Terms

Residual Graph: a graph with some flow
Augmenting Path: a path from s to t

Algorithms for Max-Flow

Ford-Fulkerson
– Calculate C = min( {sum of capacity from source}, {sum of capacity to sink} )
– Total complexity: O( ( |V| + |E| ) C )

Scaling Ford-Fulkerson
– Calculate C = {sum of capacity from source}
– Total complexity: O( |E|^2 log C )

Edmonds-Karp
– Total complexity: O( |E|^2 |V| )
– This algorithm’s complexity does not depend on C, and thus the algorithm is strongly polynomial

Preflow-Push
– Total complexity: O(|V|^2 |E| )
– This algorithm works even if there are edges whose capacities are irrational numbers