2013/09/10 by Rahul Mehta, Mehta, Rahul · 1 citation
Computer Science · #05C21 #68R10 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #acm:05C21 #acm:68R10 #cs.DS #msc:05C21 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1309.2525
This paper has been withdrawn due to issues relating to nonsaturating pushes and the validity of the labeling. A slightly modified result is contained in the paper "A New Push-Relabel Algorithm for the Max-Flow Problem"
arxiv created 2013/10/29 · arxiv updated 2013/10/30
In this paper, we present an improved algorithm for the maximum flow problem on general networks with n vertices and m arcs. We show how to solve the problem in O(mn) time, when m = O(n2-ε), for some 0 <ε≤ 1. This improves upon the results of both Orlin and King, et. al., who solved the problem in O(mn + m31/16 log2 n) and O(mnlogm/nlog nn) time, respectively. Our main result is reducing the number of nonsaturating pushes to O(mn) across all scaling phases. Our algorithm can be seen as complementary to King, et. al., in the sense that we solve the max-flow problem in O(mn) time when m = O(n2-ε) (all sparse and non-dense networks), whereas King, et. al. solve it in O(mn) time when m = Ω(n1+ε) (all dense and non-sparse networks). Our improvement is reached by a novel combination of Ahuja and Orlin's excess scaling method and Orlin's compact flow networks. To our knowledge, this is the first O(mn) time max-flow algorithm that runs on this range of networks. Further, we extend the range of Orlin's O(mn) time algorithm from O(n16/15-ε) to O(n2-ε), which is an improvement of approximately O(n0.94). Our result also establishes that the problem can be solved for all n and m using exclusively the push-relabel method. We also give improved algorithms for parametric flows and efficiently constructing Gomory-Hu trees, and suggest a new approach to the minimum-cost flow problem.