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

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.