Max flow problem
programming
Statement
Max-flow problem
Given a flow network $(G, c, s, t)$ what is the max value a flow on this network can have?
Solutions
- Ford-Fulkerson Algorithm
- $O(C \vert E \vert)$ where $C$ is the max flow.
- This is only guaranteed to terminate for integer flows.
- Edmonds-Karp algorithm
- $O(\vert E \vert^2 \cdot \vert V \vert)$ run time.
- Assumes positive flow values.
Theory
- Max-flow min-cut Theorem
- This says the solutions are the same as the min st-cut problems.