Search for a network edge connection using the maximum flow algorithm

Question

I want to find boundary connectivity (i.e. the minimum number of edges to remove to disable the 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 the graph, but this will lead to the number of networks of the flow O (| V | ^ 2),

int Edge-Connectivity(Graph G){ int min = infinite; for (Vertex u: GV){ for (Vertex v: GV){ 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 would like to do it with | V | (the maximum flow algorithm is executed only for O (| V |) times) instead of O (| V | ^ 2) of them

Answer 1

Divide a node v on your graph. For each w , except v , calculate the maximum flow from v to w . Since v must be on one side of the global global section, and something else must be on the other side, one of these flows will determine the global minimum section.

There is a trick due to Hao and Orlin, where if you use the press push algorithm, the global calculation of the minimum cut takes about the same time as the minimum (s, t) -cut. This is of practical importance. Karger has a randomized algorithm that does this in O (n polylog (n)) time, but I don't know any implementations, let alone fast implementations.