# [Algorithms] Network Flow

#### 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.