Max flow problem O(n^3) by Karzanov
Posted: Wed Mar 19, 2003 8:35 am
Can you show me the Max flow problem O(n^3)
The algorithm you are talking about is I think using preflows, or sth like that. I know that it's pretty hard to understand and even harder to explain. There is a different algorithm though, with complexity O(mn*(m+n)), where m=number of edges and n=number of vertices. It uses the Ford-Fulkerson method with bfs for finding the extending routes.
You can read about both algorithms in "Introduction to algorithms".