#### Steps

Input & Output

High level description: base case + induction

Complexity: how much each step cost + how many steps

Proof: base case + induction

Leave a reply

Input & Output

High level description: base case + induction

Complexity: how much each step cost + how many steps

Proof: base case + induction

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

Residual Graph: a graph with some flow

Augmenting Path: a path from s to t

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