A cut C in a network is a set of nodes that is neither empty nor the entire set of nodes. The weight of a cut is the sum of the weights of the edges having exactly one endpoint in C.
| int | MIN_CUT(const graph& G, const edge_array<int>& weight, list<node>& C, bool use_heuristic = true) | |
| MIN_CUT takes a graph G and an edge_array weight that gives for
each edge a non-negative integer weight.
The algorithm ([82]) computes
a cut of minimum weight. A cut of minimum weight is returned in C
and the value of the cut is the return value of the function.
The running time is
O(nm + n2log n). The function uses a heuristic to speed up its computation.
Precondition The edge weights are non-negative. |
||
| list<node> | MIN_CUT(const graph& G, const edge_array<int>& weight) | |
| as above, but the cut C is returned. | ||
| int | CUT_VALUE(const graph& G, const edge_array<int>& weight, const list<node>& C) | |
| returns the value of the cut C. | ||