Network Flow and Testing Graph Connectivity

An algorithm of Dinic for finding the maximum flow in a network is described. It is then shown that if the vertex capacities are all equal to one, the algorithm requires at most O (|V|^1/2 |E|) time, and if the edge capacities are all equal to one, the algorithm requires at most O (|V|^2/3 |E|) time. Also, these bounds are tight for Dinic’s algorithm. These results are used to test the vertex connectivity of a graph in O (|V|^1/2 |E|²) time and the edge connectivity in O (|V|^5/3 |E|) time.