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

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

0.00 Avg rating0 Votes
Article ID: iaor200942189
Country: United States
Volume: 56
Issue: 4
Start Page Number: 992
End Page Number: 1009
Publication Date: Jul 2008
Journal: Operations Research
Authors:
Abstract:

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. Once the maximum blocking–cut solution is available, the additional complexity required to find the respective maximum–flow is O(m log n). A variant of the algorithm is a new parametric maximum–flow algorithm generating all breakpoints in the same complexity required to solve the constant capacities maximum–flow problem. The pseudoflow algorithm has also a simplex variant, pseudoflow–simplex, that can be implemented to solve the maximum–flow problem. One feature of the pseudoflow algorithm is that it can initialize with any pseudoflow. This feature allows it to reach an optimal solution quickly when the initial pseudoflow is ‘close’ to an optimal solution. The complexities of the pseudoflow algorithm, the pseudoflow–simplex, and the parametric variants of pseudoflow and pseudoflow–simplex algorithms are all O(mn log n) on a graph with n nodes and m arcs. Therefore, the pseudoflow–simplex algorithm is the fastest simplex algorithm known for the parametric maximum–flow problem. The pseudoflow algorithm is also shown to solve the maximum–flow problem on s, t–tree networks in linear time, where s, t–tree networks are formed by joining a forest of capacitated arcs, with nodes s and t adjacent to any subset of the nodes.

Reviews

Required fields are marked *. Your email address will not be published.