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|2log| V|).
Precondition: The edge weights are non-negative. |