2012/05/19 by Dorit S. Hochbaum, James B. Orlin
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Machine Learning and Algorithms
paper · doi:10.1002/net.21467
crossref issued 2012/05/19 · crossref published 2012/05/19 · crossref published-online 2012/05/19 · openalex publication_date 2012/05/19 · crossref created 2012/05/20 · crossref published-print 2013/01/01 · crossref deposited 2023/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21 · crossref indexed 2026/07/30
Abstract 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 algorithm is very efficient in practice, and that the highest label version of the algorithm tends to perform best. Here, we improve the running time of the highest label pseudoflow algorithm to O ( n 3 ) using simple data structures and to O ( nm log ( n 2 / m )) using the dynamic trees data structure. Both these algorithms use a new form of Depth‐First‐Search implementation that is likely to be fast in practice as well. In addition, we give a new simpler description of the pseudoflow algorithm by relating it to the simplex algorithm as applied to the maximum preflow problem defined here. The interpretation of the generic pseudoflow algorithm as a simplex‐like algorithm for the maximum preflow problem motivates the pseudoflow algorithm and highlights differences between the pseudoflow algorithm and the preflow‐push algorithm of Goldberg and Tarjan. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013