On the maximum capacity augmentation algorithm for the maximum flow problem (Q1314319)

The subject of this paper is two variants of the classical path- augmentation algorithm for maximum capacitated flow problem. The main point of the paper is that both algorithms have polynomial bounds even when the capacities have real values. The first bound is \(O(m^ 2\log m)\) flow augmentations and \(O(m^ 3\log m)\) operations. In the second case, a network simplex implementation, the number of simplex pivots is bounded by \(O(m^ 2 n^ 2\log m)\) and the number of operations by \(O(m^ 2 n^ 3\log m)\), where \(m\) is the number of arcs and \(n\) the number of nodes.