next up previous contents
Next: Maximum Cardinality Matchings in Up: Graphs Algorithms Previous: Min Cost Flow Algorithms

   
Minimum Cut (min_cut)

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.



LEDA research project
1998-10-02