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

LEDA research project
1999-04-23

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