Statement
Max-flow problem
Given a flow network
what is the max value a flow on this network can have?
Solutions
- Ford-Fulkerson Algorithm
where is the max flow. - This is only guaranteed to terminate for integer flows.
- Edmonds-Karp algorithm
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.