Worst case behavior of the Dinic algorithm

Abstract

Many max-flow phase algorithms use the Dinic algorithm to generate an acyclic network in the first phase, and then solve the maximal flow problem in such a network in the second phase. This process is then repeated until the maximum value flow is found in the original network. In this paper a class of networks is presented where the Dinic algorithm always attains it's worst case bound. The Dinic algorithm requires (n - 1) network generations, where n is the number of nodes in the original network for finding the maximum value flow in the original network.