Max flow problem O(n^3) by Karzanov

msn · Post by **msn** » Wed Mar 19, 2003 8:35 am

Can you show me the Max flow problem O(n^3)

makbet · Post by **makbet** » Thu Mar 20, 2003 5:52 pm

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".

msn · Post by **msn** » Fri Mar 21, 2003 12:18 pm

I know Ford-Fulkerson but i want a better algorithm. Can you show me? Not only O(n^3).