Max Flow Problem

Theory

s-t-Cut
Residualgraph
Flow Augmenting Paths
Flow Optimality criteria
Max-Flow Min-Cut Theorem
Blocking Flows
Simple s-t-Networks
Preflows

Algotithm

Ford & Fulkerson $O(m\cdot M)$
Edmonds and Karp Algoritums $O(m^2\cdot n)$
Dinitz’ Algorithm $O(n^2\cdot m)$ in Bipatiter Graph $O(m\cdot \sqrt{n})$
Preflow Push $O(n^2\cdot m)$
Max-Height Algorithm $O(n^2\cdot \sqrt{m})$

Maximaler Flusswert: $M$
Menge an Vertices: $n$
Menge an Kanten: $m$