A cut in a network is a set S of nodes that is neither empty nor the entire set of nodes. The weight of a cut is the sum of the weight of the edges having exactly one endpoint in S.
list<node> | MIN_CUT(graph G, edge_array<int>& weight) | |
MIN_CUT(G, weight) takes as arguments a graph G and an edge_array
giving for each edge an integer weight. The algorithm ([72]) computes
the cut of minimum weight and returns it as a list of nodes. It
has running time O(|V| * |E| + |V| ^2 log |V|).
Precondition: The edge weights are non-negative. |