Implementing Goldber’s max-flow-algorithm-A computational investigation

This paper reviews Goldberg’s algorithm for solving max-flow-problems on networks and discusses several ideas for implementing and enhancing this approach. It presents computational results for these implementations and compares its best Goldberg-codes with implementations of Dinic’s and Karzanov’s method presented in literature. The present results show that the implementations of Goldberg’s algorithm outperform the other codes significantly. Here the essential breakthrough is obtained by the use of a modification of Goldberg’s basic labeling scheme by which the number of labeling steps is reduced drastically.