This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Hochbaum, D. S. Search for Related Content

The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem

Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley, California 94720
hochbaum{at}ieor.berkeley.edu

We introduce the pseudoflow algorithm for the maximum-flow problem that employs only pseudoflows and does not generate flows explicitly. The algorithm solves directly a problem equivalent to the minimum-cut problem—the maximum blocking-cut problem. Once the maximum blocking-cut solution is available, the additional complexity required to find the respective maximum-flow is O(m log n). A variant of the algorithm is a new parametric maximum-flow algorithm generating all breakpoints in the same complexity required to solve the constant capacities maximum-flow problem. The pseudoflow algorithm has also a simplex variant, pseudoflow-simplex, that can be implemented to solve the maximum-flow problem. One feature of the pseudoflow algorithm is that it can initialize with any pseudoflow. This feature allows it to reach an optimal solution quickly when the initial pseudoflow is "close" to an optimal solution. The complexities of the pseudoflow algorithm, the pseudoflow-simplex, and the parametric variants of pseudoflow and pseudoflow-simplex algorithms are all O(mn log n) on a graph with n nodes and m arcs. Therefore, the pseudoflow-simplex algorithm is the fastest simplex algorithm known for the parametric maximum-flow problem. The pseudoflow algorithm is also shown to solve the maximum-flow problem on s, t-tree networks in linear time, where s, t-tree networks are formed by joining a forest of capacitated arcs, with nodes s and t adjacent to any subset of the nodes.

Subject classifications: flow algorithms; parametric flow; normalized tree; lowest label; pseudoflow algorithm; maximum flow.
History: Received May 2001; revision received May 2007; accepted May 2007.

This article has been cited by other articles:

				B. G. Chandran and D. S. Hochbaum A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem Operations Research, March 1, 2009; 57(2): 358 - 376. [Abstract] [PDF]