The maximum flow problem: A max-preflow approach

In the first part of the paper a general maximum flow procedure, which finds a maximum preflow and converts it into a maximum flow, is defined using a non-standard presentation of the maximum flow problem, which is viewed as a particular case of the maximum preflow one. This procedure enables several significant max-flow algorithms to be derived by instantiation, including the ones based on Goldberg’s approach and the so-called ‘distance directed’ algorithms. Moreover, with this procedure a new max-flow algorithm can be defined, parametric with respect to the bound k on the length of the flow push paths. This procedure represents a generalization both of Goldberg’s approach and of the ‘distance directed’ algorithm DD1. In the second part, some interesting results from a wide computational experimentation on max-flow algorithms are presented.