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

Bala G. Chandran () and Dorit S. Hochbaum ()
Additional contact information
Bala G. Chandran: Analytics Operations Engineering, Inc., Boston, Massachusetts 02109
Dorit S. Hochbaum: Department of Industrial Engineering and Operations Research, and Walter A. Haas School of Business, University of California, Berkeley, California 94720

Operations Research, 2009, vol. 57, issue 2, 358-376

Abstract: 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.

Keywords: flow algorithms; parametric flow; normalized tree; lowest label; pseudoflow algorithm; maximum flow (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0572 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:2:p:358-376

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().