Stoer–Wagner algorithm
In graph theory, the Stoer–Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights.
It was proposed by Mechthild Stoer and Frank Wagner in 1995.
The essential idea of this algorithm is to shrink the graph by merging the most intensive vertices, until the graph only contains two combined vertex sets.
[2] At each phase, the algorithm finds the minimum
A cut is a partition of the vertices of a graph into two non-empty, disjoint subsets.
In practice, the minimum cut problem is always discussed with the maximum flow problem, to explore the maximum capacity of a network, since the minimum cut is a bottleneck in a graph or network.
Therefore, the global min-cut can be found by checking the graph
of the graphs vertices grows starting with an arbitrary single vertex until
This procedure can be formally shown as:[2] add vertex
[4] After one phase of the MinimumCutPhase, the two vertices are merged as a new vertex, and edges from the two vertices to a remaining vertex are replaced by an edge weighted by the sum of the weights of the previous two edges.
Edges joining the merged nodes are removed.
In addition, the MinimumCut would record and update the global minimum cut after each MinimumCutPhase.
By merging them into node 1+5, the new graph is as shown in step 2.
In this phase, the weight of cut is 5, which is the summation of edges (1,2) and (1,5).
The next heaviest edges is (2,3) or (1+5,6), we choose (1+5,6) thus node 6 is added to the set.
Then we compare edge (2,3) and (6,7) and choose node 3 to put in set
cut of the graph, where s and t are the two vertices last added in the phase.
Observe that a single run of MinimumCutPhase gives us an ordering of all the vertices in the graph (where
We prove the lemma by induction on the set of active vertices.
is always an active vertex since the last cut of the phase separates
runs of MinimumCutPhase, which is called on graphs with decreasing number of vertices and edges.
For the MinimumCutPhase, a single run of it needs at most
Therefore, the overall running time should be the product of two phase complexity, which is
[2] For the further improvement, the key is to make it easy to select the next vertex to be added to the set
reside in a priority queue based on a key field.
is the sum of the weights of the edges connecting it to the current
has to be deleted from the queue, and the key of every vertex
By using the Fibonacci heap we can perform an ExtractMax operation in
amortized time and an IncreaseKey operation in
Thus, the time we need for this key step that dominates the rest of the phase, is
