Bottlenecks and Edge Connectivity in Unsymmetrical Networks

Let Fu,v be the maximal flow from u to v in a network N = (V,E,c). We construct the matrix (min \ Fu,v ,Fv,u \ |u,v ∈ V) by solving |V|log 2|V| individual max-flow problems for N. There is a tree network N = (V, E, c) that stores minimal cuts corresponding to min \ Fu,v, Fv,u \ for all $u,v$. N̄ can be constructed by solving |V|log 2|V| individual max flow problems for the given network which can be done within O(|V|⁴ ) steps using the Dinic–Karzanov algorithm. We design an algorithm that computes the edge connectivity k of a directed graph within O(k· |E|· |V|) steps.