More Web Proxy on the site http://driver.im/

article

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

Authors:

Bala G. Chandran,

Dorit S. HochbaumAuthors Info & Claims

Operations Research, Volume 57, Issue 2

Pages 358 - 376

https://doi.org/10.1287/opre.1080.0572

Published: 01 March 2009 Publication History

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.

References

[1]

Ahuja, R. K., Magnanti, T. L. and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.

Digital Library

[2]

Ahuja, R. K., Kodialam, M., Mishra, A. K. and Orlin, J. B., "Computational investigations of maximum flow algorithms," Eur. J. Oper. Res., v97, pp. 509-542, 1997.

[3]

Anderson, C. and Hochbaum, D. S., "The performance of the pseudoflow algorithm for the maximum flow and minimum cut problems," 2002.

[4]

Anderson, R. J., Setubal, J. C., Johnson, D. S. and McGeoch, C. C., "Goldberg's algorithm for the maximum flow in perspective: A computational study," Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, Providence, RI, pp. 1-18, 1993.

[5]

2007.

[6]

Chandran, B. and Hochbaum, D. S., "Pseudoflow solver," 2007.

[7]

Derigs, M. and Meier, W., "Implementing Goldberg's max-flow algorithm---A computational investigation," ZOR---Methods and Models Oper. Res., v33, pp. 383-403, 1989.

[8]

"The first DIMACS algorithm implementation challenge: The core experiments," 1990.

[9]

Dinic, E. A., "Algorithm for the solution of a problem of maximal flow in networks with power estimation," Soviet Math. Doklady, v11, pp. 1277-1280, 1970.

[10]

Ford, L. R. and Fulkerson, D. R., "Maximal flow through a network," Canadian J. Math., v8, pp. 339-404, 1956.

[11]

Goldberg, A. V., "Andrew Goldberg's network optimization library," 2007.

[12]

Goldberg, A. V. and Cherkassky, B. V., "On implementing the push-relabel method for the maximum flow problem," Algorithmica, v19, pp. 390-410, 1997.

[13]

Goldberg, A. V. and Rao, S., "Beyond the flow decomposition barrier," J. ACM, v45, pp. 783-797, 1998.

Digital Library

[14]

Goldberg, A. V. and Tarjan, R. E., "A new approach to the maximum flow problem," J. ACM, v35, pp. 921-940, 1988.

Digital Library

[15]

Goldfarb, D. and Grigoriadis, M., "A computational comparison of the Dinic and network simplex algorithms for maximum flow," Ann. Oper. Res., v13, pp. 83-123, 1988.

[16]

Hochbaum, D. S., "The pseudoflow algorithm: A new algorithm for the maximum flow problem," Oper. Res., v56, pp. 992-1009, 2008.

Digital Library

[17]

Hochbaum, D. S. and Orlin, J. B., "The pseudoflow algorithm in O(mnlog(n2/m)) and O(n3)," 2007.

[18]

Lerchs, H. and Grossman, I., "Optimum design of open pit mines," Trans., Canadian Inst. Mining and Metallurgy, v68, pp. 17-24, 1965.

[19]

Picard, J., "Maximal closure of a graph and applications to combinatorial problems," Management Sci., v22, pp. 1268-1272, 1976.

Digital Library

[20]

Sleator, D. D. and Tarjan, R. E., "A data structure for dynamic trees," J. Comp. System Sci., v26, pp. 362-391, 1983.

Digital Library

Cited By

Rozenshtein PPreti GGionis AVelegrakis Y(2020)Mining Dense Subgraphs with Similar EdgesMachine Learning and Knowledge Discovery in Databases10.1007/978-3-030-67664-3_2(20-36)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-67664-3_2
Kagaris DDutta S(2019)Scheduling Mutual Exclusion Accesses in Equal-Length JobsACM Transactions on Parallel Computing10.1145/33425626:2(1-26)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3342562
Kara GÖzturan C(2019)Algorithm 1002ACM Transactions on Mathematical Software10.1145/333048145:4(1-28)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3330481
Show More Cited By

A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

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

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. ...
Simplifications and speedups of the pseudoflow algorithm

The pseudoflow algorithm for solving the maximum flow and minimum cut problems was devised in Hochbaum (2008). The complexity of the algorithm was shown in (2008) to be O(nm log n). Chandran and Hochbaum, (2009) demonstrated that the pseudoflow ...
Implementations of the pseudoflow algorithm for maximum flow, bipartite matching, flows in unit capacity networks, and parametric maximum flow

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 57, Issue 2

March 2009

270 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 March 2009

Accepted: 01 March 2008

Received: 01 January 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rozenshtein PPreti GGionis AVelegrakis Y(2020)Mining Dense Subgraphs with Similar EdgesMachine Learning and Knowledge Discovery in Databases10.1007/978-3-030-67664-3_2(20-36)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-67664-3_2
Kagaris DDutta S(2019)Scheduling Mutual Exclusion Accesses in Equal-Length JobsACM Transactions on Parallel Computing10.1145/33425626:2(1-26)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3342562
Kara GÖzturan C(2019)Algorithm 1002ACM Transactions on Mathematical Software10.1145/333048145:4(1-28)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3330481
Hochbaum DLiu S(2018)Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit ManufacturingOperations Research10.1287/opre.2018.174166:6(1571-1585)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1287/opre.2018.1741
Greco SMolinaro CPulice CQuintana XShin SShin DLencastre M(2017)Incremental maximum flow computation on evolving networksProceedings of the Symposium on Applied Computing10.1145/3019612.3019816(1061-1067)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3019612.3019816
Hochbaum D(2016)A polynomial time repeated cuts algorithm for the time cost tradeoff problemComputers and Industrial Engineering10.1016/j.cie.2016.02.01895:C(64-71)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.cie.2016.02.018
Fishbain BHochbaum DMueller S(2016)A competitive study of the pseudoflow algorithm for the minimum s---t cut problem in vision applicationsJournal of Real-Time Image Processing10.1007/s11554-013-0344-311:3(589-609)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s11554-013-0344-3
Laube UNebel M(2016)Maximum Likelihood Analysis of the Ford---Fulkerson Method on Special GraphsAlgorithmica10.1007/s00453-015-9998-574:4(1224-1266)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00453-015-9998-5
Sirisrisakulchai JHarnpornchai NAutchariyapanitkul KSriboonchitta S(2016)A Flood Risk Assessment Based on Maximum Flow Capacity of Canal SystemIntegrated Uncertainty in Knowledge Modelling and Decision Making10.1007/978-3-319-49046-5_12(136-148)Online publication date: 30-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-49046-5_12
Homayounnejad SBagheri A(2015)An efficient distributed max-flow algorithm for Wireless Sensor NetworksJournal of Network and Computer Applications10.1016/j.jnca.2015.04.00454:C(20-32)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.04.004
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents