Browse Theses

We present a comprehensive experimental evaluation of Hochbaum's pseudoflow algorithm for the maximum flow and minimum cut problems. We develop several implementations of the pseudoflow algorithm, and compare them to the best known implementation of Goldberg and Tarjan's push-relabel algorithm on several benchmark and randomly generated instances. The experiments demonstrate that the pseudoflow implementations are faster than push-relabel, and also provide insights into key differences between the two algorithms.

We then examine properties of the pseudoflow algorithm when applied to two special cases of the maximum flow problem: flows in unit capacity networks and maximum cardinality bipartite matching. We develop pseudoflow implementations that exploit these properties, and compare them on several benchmark unit capacity flow and matching instances to state-of-the-art implementations of push-relabel and augmenting path algorithms that are specifically designed to solve these problems. The experiments show that the pseudoflow variants are generally faster than the other algorithms.

We also propose the matching-pseudoflow algorithm, a variant of the pseudoflow algorithm for bipartite matching. For a graph with n nodes, m arcs, n ₁ the size of the smaller set in the bipartition, and the maximum matching value ý ý n ₁, the algorithm's complexity is O (min{n ₁ý, m } + k min{ý 2 , m }). Using boolean operations on words of size ý, the complexity of the matching-pseudoflow algorithm is further improved to O (min{ n ₁ý, n ₁ n ₂ l , m } + ý 2 + k ^2.5 l ), which is faster than previous algorithms such as Cheriyan and Mehlhorn's algorithm with complexity O ( n ^2.5 l ). We show that it is possible to adapt either push-relabel or the Hopcroft-Karp algorithm to achieve the same complexity as the matching-pseudoflow algorithm that does not use word operations.

Finally, we develop an implementation of the pseudoflow algorithm for the parametric maximum flow problem, and apply it to a problem motivated by medical image segmentation.