This Article Full Text (PDF) 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 Google Scholar Google Scholar Articles by Chandran, B. G. Articles by Hochbaum, D. S. Search for Related Content

A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem

Analytics Operations Engineering, Inc., Boston, Massachusetts 02109
Department of Industrial Engineering and Operations Research, and Walter A. Haas School of Business, University of California, Berkeley, California 94720
bchandran{at}nltx.com
hochbaum{at}ieor.berkeley.edu

We present the results of a computational investigation of the pseudoflow and push-relabel algorithms for the maximum flow and minimum s-t cut problems. The two algorithms were tested on several problem instances from the literature. Our results show that our implementation of the pseudoflow algorithm is faster than the best-known implementation of push-relabel on most of the problem instances within our computational study.

Subject classifications: flow algorithms; parametric flow; normalized tree; lowest label; pseudoflow algorithm; maximum flow.
History: Received January 2006; revision received December 2007; accepted March 2008.