Minimum Graph Cut
A Minimum Graph Cut is a graph cut such that, given cutset function (e.g. edge weight sum), is not larger than for any other graph cut.
- AKA: Min-Cut.
- Context:
- It can be the output of a Graph Min-Cut Task.
- …
- Counter-Example(s):
- See: Normalized Graph Min-Cut, Bridge (Graph Theory), Max-Flow Min-Cut Theorem, Flow Network, Edmonds-Karp Algorithm, Set Partition, Maximum Flow Problem.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/cut_(graph_theory)#Minimum_cut Retrieved:2014-5-4.
- A cut is minimum if the size of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.
The max-flow min-cut theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There are polynomial-time methods to solve the min-cut problem, notably the Edmonds-Karp algorithm.
- A cut is minimum if the size of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/minimum_cut Retrieved:2014-5-4.
- In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.
For a graph G = (V, E), the problem can be reduced to 2|V| − 2 = O(|V|) maximum flow problems, equivalent to O(|V|) s − t cut problems by the max-flow min-cut theorem. Hao and Orlin have shown an algorithm to compute these max-flow problems in time asymptotically equal to one max-flow computation, requiring O(|V|×|E| log(|V|2/|E|)) steps. Asymptotically faster algorithms exist for directed graphs, though these do not necessarily extend to the undirected case. A study by Chekuri et al. established experimental results with various algorithms. [1]
- In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.
- ↑ (Also NEC Research Institute Technical Report 96-132, 1996)
2002
- http://valis.cs.uiuc.edu/~sariel/teach/2002/a/notes/min_cut.pdf
- QUOTE: Compute the cut with minimum number of edges in the graph. Namely, find [math]\displaystyle{ S \subset V }[/math] such that [math]\displaystyle{ (S \times (V−S)) \cap E }[/math] is as small as possible, and [math]\displaystyle{ S }[/math] is neither empty nor all the vertices of the graph [math]\displaystyle{ G = (V,E) }[/math].
1997
- (Chekuri et al., 1997) ⇒ Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. (1997). “Experimental Study of Minimum Cut Algorithms.” In: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms (SODA 1997).
1994
- (Jianxiu & Orlin, 1994) ⇒ Jianxiu Hao, and James B. Orlin. (1994). “A Faster Algorithm for finding the Minimum Cut in a Directed Graph". In: J. Algorithms, 17.