Finding edge connectivity of a network by using Ma

问题:

I want to find the edge connectivity (i.e. minimum number of edges to remove to disconnect a graph) of an undirected graph using maximum flow algorithms (Edmond Karp / Ford-Fulkerson algorithms) ,

I know that I can accomplish this task by finding the minimum maximum flow between every two nodes of a graph , but this would result O(|V| ^ 2) number of flow networks ,

int Edge-Connectivity(Graph G){
    int min = infinite;
    for (Vertex u: G.V){
        for (Vertex v: G.V){
           if (u != v){ 
             //create directed graph Guv (a graph with directed edges and source u and sink v)
             //run Edmonds-Karp algorithm to find the maximum flow |f*|
             if (min > |f*|)
               min = |f*|;
           }    
         }
     }
     return min;
}

But I'd like to do this with |V| flow networks (running the max flow algorithm for only O(|V|) times) instead of O(|V| ^ 2) of them

回答1:

Distinguish a node v in your graph. Compute, for every w other than v, the maximum flow from v to w. Since v must be on one shore of the graph's global minimum cut and something else must be on the other side, one of these flows will identify the global minimum cut.

There's a trick due to Hao and Orlin where, if you use a preflow push algorithm, a global minimum-cut computation takes about as much time as a minimum (s,t)-cut problem. It has the benefit of being practical. Karger has a randomised algorithm that does it in O(n polylog(n)) time, but I'm not aware of any implementations, let alone fast implementations.