About preflow algorithms for the minimum flow problem
Laura Ciupală, Eleonor Ciurea · WSEAS Transactions on Computers archive · 2008
In this paper, we describe the highest-label preflow algorithm for minimum flow. This algorithm is a special implementation of the generic preflow algorithm developed by Ciurea and Ciupala in [8], obtained by imposing in the generic preflow algorithm the rule that the algorithm must always select an active node with the highest distance label. Our new algorithm runs in O(n2m1/2) time, which is substantially better than the running time of the generic preflow algorithm, that is O(n2m). Moreover, the highest-label preflow algorithm is the fastest polynomial algorithm for minimum flow problem.