Improving time bounds on maximum generalised flow computations by contracting the network

We consider the maximum generalised network flow problem and a supply-scaling algorithmic framework for this problem. We present three network-modification operations, which may significantly decrease the size of the network when the remaining node supplies become small. We use these three operations in Goldfarb et al.'s supply-scaling algorithm and prove an O(m(2) n log B) bound on the running time of the resulting algorithm. The previous best time bounds on computing maximum generalised flows are the O(m(1.5) n(2) log B) bound of Kapoor and Vaidya's algorithm based on the interior-point method, and the O(m(3) log B) bound of Goldfarb et al.'s algorithm. (C) 2003 Elsevier B.V. All rights reserved.