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 S 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 S.

int MIN_CUT(graph G, 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 ([73]) 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 + n²log n). The function uses a heuristic to speed up its computation.
Precondition The edge weights are non-negative.

list<node> MIN_CUT(graph G, edge_array<int> weight)

as above, but the cut C is returned.

int CUT_VALUE(graph G, edge_array<int> weight, list<node> C)

returns the value of the cut C.

Next: Maximum Cardinality Matchings in Up: Graph Algorithms Previous: Min Cost Flow Algorithms Contents Index

LEDA research project
2000-02-09

int	MIN_CUT(graph G, 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 ([73]) 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 + n²log n). The function uses a heuristic to speed up its computation. Precondition The edge weights are non-negative.
list<node>	MIN_CUT(graph G, edge_array<int> weight)
		as above, but the cut C is returned.
int	CUT_VALUE(graph G, edge_array<int> weight, list<node> C)
		returns the value of the cut C.