The performance of maximum-flow algorithms that work in phases is studied as a function of the maximum arc capacity, C, of the network and a quantity we call the total potential, P of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tight O(min{C1’/3ℝVℝ2’/3,P1’/2,ℝVℝ}) upper bound on the number of phases. An O(min{PlogℝVℝ,CℝVℝ3’/2,ℝVℝ2ℝEℝ}) upper bound is derived on the total length of the augmenting paths used by Dinic’s algorithm. The latter quantity is useful in estimating the performance of Dinic’s method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic’s algorithm is significantly better than would be apparent from a bound based on ℝVℝ and ℝEℝ alone. We present an application of our bounds to the maximum subgraph density problem.
