James B. Orlin
ABSTRACT
In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m31/16 log2 n) time. In the case that m = O(n1.06), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm logm/(n log n)n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n2/ log n).
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993. Google Scholar
Digital Library
- G. Blelloch, V. Vassilevska, and R. Williams. A new combinatorial approach for sparse graph problems. Automata, Languages and Programming, pages 108--120, 2008. Google ScholarDigital Library
- B. Chandran and D. Hochbaum. A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Operations research, 57(2):358, 2009. Google ScholarDigital Library
- B. Cherkassky and A. Goldberg. On implementing the push--relabel method for the maximum flow problem. Algorithmica, 19(4):390--410, 1997.Google ScholarCross Ref
- L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.Google ScholarCross Ref
- H. Gabow and R. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences, 30(2):209--221, 1985.Google Scholar
- A. V. Goldberg and S. Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45:783--797, 1998. Google ScholarDigital Library
- G. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(0):273--281, 1986. Google ScholarDigital Library
- V. King, S. Rao, and R. Tarjan. A faster deterministic maximum flow algorithm. J. Algorithms, 23:447--474, 1994. Google ScholarDigital Library
- D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Computer and System Sciences, 24:362--391, 1983. Google ScholarDigital Library
Index Terms
- Max flows in O(nm) time, or better
Recommendations
Approximate max flow on small depth networks
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer ScienceThe author considers the maximum flow problem on directed acyclic networks with m edges and depth r (length of the longest s-t path). The main result is a new deterministic algorithm for solving the relaxed problem of computing an s-t flow of value at ...
Single Source -- All Sinks Max Flows in Planar Digraphs
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer ScienceLet $G = (V, E)$ be a planar $n$-vertex digraph. Consider the problem of computing max $st$-flow values in $G$ from a fixed source $s$ to all sinks $t \in V \set minus \{s\}$. We show how to solve this problem in near-linear $O(n \log^3 n)$ time. ...
Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back
FOCS '13: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer ScienceWe present an m(10/7)= (m1.43-time We recall that f denotes O(f poly(log f)). algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the ...
Comments