非表示:
キーワード:
-
要旨:
The Stoer–Wagner algorithm computes a minimum cut in a weighted undirected
graph. The algorithm works in n−1 phases, where n is the number of nodes of G.
Each phase takes time O(m+nlogn), where m is the number of edges of G, and
computes a pair of vertices s and t and a minimum cut separating s and t. We
show how to extend the algorithm such that each phase also computes a maximum
flow from s to t. The flow is computed in O(m) additional time and certifies
the cut computed in the phase.
