TOPICS
Search

Mincut


Let G=(V,E) be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut C of G is any nontrivial subset of V, and the weight of the cut is the sum of weights of edges crossing the cut. A mincut is then defined as a cut of G of minimum weight. The problem is polynomial time solvable as a series of network flow problems or using the algorithm of Stoer and Wagner (1994).


See also

Boolean Function, Cut, Maxcut, Minimum Vertex Cut, Network Flow, Weighted Graph

Explore with Wolfram|Alpha

References

Stoer, M. and Wagner, F. "A Simple Min Cut Algorithm." Algorithms--ESA '94, LNCS 855, 141-147, 1994.

Referenced on Wolfram|Alpha

Mincut

Cite this as:

Weisstein, Eric W. "Mincut." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Mincut.html

Subject classifications