Wednesday, May 23, 2012 - 13:00
1 hour (actually 50 minutes)
Over the past 30 years, researchers have developed successively faster algorithms for the maximum flow problem. The best strongly polynomial time algorithms have come very close to O(nm) time. Many researchers have conjectured that O(nm) time is the "true" worst case running time. We resolve the issue in two ways. First, we show how to solve the max flow problem in O(nm) time. Second, we show that the running time is even faster if m = O(n). In this case, the running time is O(n^2/log n).