next up previous contents index
Next: Maximum Cardinality Matchings in Up: Graph Algorithms Previous: Min Cost Flow Algorithms   Contents   Index


Minimum Cut ( min_cut )

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 .


next up previous contents index
Next: Maximum Cardinality Matchings in Up: Graph Algorithms Previous: Min Cost Flow Algorithms   Contents   Index
Christian Uhrig 2017-04-07