Minimum Graph Cut

From GM-RKB
(Redirected from minimum cut)
Jump to navigation Jump to search

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.



References

2014



  • (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]

  1. (Also NEC Research Institute Technical Report 96-132, 1996)

2002

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.