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

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Ahuja R. K., Kodialam M., Mishra A. K., Orlin J. B. Computational investigations of maximum flow algorithms. Eur. J. Oper. Res. (1997) 97(3):509–542Crossref, Google Scholar
• Anderson C., Hochbaum D. S. The performance of the pseudoflow algorithm for the maximum flow and minimum cut problems. (2002) . Manuscript, University of California, BerkeleyGoogle Scholar
• Anderson R. J., Setubal J. C., Johnson D. S., McGeoch C. C. Goldberg's algorithm for the maximum flow in perspective: A computational study. Network Flows and Matching: First DIMACS Implementation Challenge (1993) (American Mathematical Society, Providence, RI) 1–18Crossref, Google Scholar
• CATS: Combinatorial Algorithms Test Sets (2007) . Retrieved January 2007, http://www.avglab.com/andrew/CATS/gens/Google Scholar
• Chandran B., Hochbaum D. S. Pseudoflow solver. (2007) . Retrieved January 2007, http://riot.ieor.berkeley.edu/riot/Applications/Pseudoflow/maxflow.htmlGoogle Scholar
• Derigs M., Meier W. Implementing Goldberg's max-flow algorithm—A computational investigation. ZOR—Methods and Models Oper. Res. (1989) 33:383–403Crossref, Google Scholar
• DIMACS The first DIMACS algorithm implementation challenge: The core experiments. (1990) . Retrieved October 2004, http://dimacs.rutgers.edu/pub/netflow/general-info/Google Scholar
• Dinic E. A. Algorithm for the solution of a problem of maximal flow in networks with power estimation. Soviet Math. Doklady (1970) 11:1277–1280Google Scholar
• Ford L. R., Fulkerson D. R. Maximal flow through a network. Canadian J. Math. (1956) 8:339–404Crossref, Google Scholar
• Goldberg A. V. Andrew Goldberg's network optimization library. (2007) . Retrieved January 2007, http://www.avglab.com/andrew/soft.htmlGoogle Scholar
• Goldberg A. V., Cherkassky B. V. On implementing the push-relabel method for the maximum flow problem. Algorithmica (1997) 19:390–410Crossref, Google Scholar
• Goldberg A. V., Rao S. Beyond the flow decomposition barrier. J. ACM (1998) 45(5):783–797Crossref, Google Scholar
• Goldberg A. V., Tarjan R. E. A new approach to the maximum flow problem. J. ACM (1988) 35(4):921–940Crossref, Google Scholar
• Goldfarb D., Grigoriadis M. A computational comparison of the Dinic and network simplex algorithms for maximum flow. Ann. Oper. Res. (1988) 13:83–123Crossref, Google Scholar
• Hochbaum D. S. The pseudoflow algorithm: A new algorithm for the maximum flow problem. Oper. Res. (2008) 56(4):992–1009Link, Google Scholar
• Hochbaum D. S., Orlin J. B. The pseudoflow algorithm in O(mnlog(n2/m)) and O(n3). (2007) . Manuscript, University of California, BerkeleyGoogle Scholar
• Lerchs H., Grossman I. Optimum design of open pit mines. Trans., Canadian Inst. Mining and Metallurgy (1965) 68:17–24Google Scholar
• Picard J. Maximal closure of a graph and applications to combinatorial problems. Management Sci. (1976) 22:1268–1272Link, Google Scholar
• Sleator D. D., Tarjan R. E. A data structure for dynamic trees. J. Comp. System Sci. (1983) 26:362–391Crossref, Google Scholar