RECENT DEVELOPMENTS IN MAXIMUM FLOW ALGORITHMS
Takao Asano, Yasuhito Asano · Journal of the Operations Research Society of Japan · 2000
Goldberg and Rao recently proposed the blocking flow method based on a binary length function to obtain a better algorithm for the maximum flow problem. The previous algorithms based on the blocking flow method proposed by Dinic use the unit length function: every residual edge is of length 1. In this paper, we survey properties of the distance function defined by a length function and give an overview on the representative maximum flow algorithms proposed so far in a systematic way by utilizing these properties. Among them are included two new algorithms: the Goldberg-Rao algorithm which finds a maximum flow on an integral capacity network N of n vertices and m edges in O(min{m^,n^}m log(n^2/m)log U) time, where U is the maximum edge capacity of N, and the Karger-Levine algorithm which finds a maximum flow on an undirected network N with unit capacity and no parallel edges in O(m + nν^) time, where ν is the value of a maximum flow of N.