Improved bounds for network flow algorithms with applications
David Fernández‐Baca · 1986
The worst-case performance of network flow problems is analyzed for unbalanced bipartite networks and for networks with small capacities. For bipartite networks where the set of nodes, S, on one side is much smaller than the set of nodes, T, on the other side, we show that any algorithm that works in phases requires at most (VBAR)S(VBAR) phases to compute a maximum flow and that Karzanov's and the MPM algorithms run in O((VBAR)S(VBAR)('2)(VBAR)T(VBAR))time. Building on previous work by Evan and Tarjan, we study the worst-case running time of algorithms that work in phases as a function of the number of vertices, (VBAR)V(VBAR), the maximum arc capacity, C, of the network and of a quantity we call the total potential, P, of the network. We prove a tight bound of O(min C('1/3)(VBAR)V(VBAR)('2/3),P('1/2) ) on the number of phases needed by any maximum flow algorithm that works in phases. Bounds are derived on the total length of the augmenting paths used by Dinic's algorithm, a quantity that is useful in estimating its performance for certain inputs. We present applications of our results to scheduling, the selection problem, the maximum subgraph density problem, and scaling maximum flow algorithms.