JavaScript is disabled for your browser. Some features of this site may not work without it.

Worst case behavior of the Dinic algorithm

Waissi, Gary R.

Waissi, Gary R.

1991

Citation:Waissi, Gary R. (1991)."Worst case behavior of the Dinic algorithm." Applied Mathematics Letters 4(5): 57-60. <http://hdl.handle.net/2027.42/29530>

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.