A Survey on Methods for finding Min-Cut Tree
Nitin Arora, Pradeep Kumar Kaushik, Surinder Pal Singh · 2013
In this paper we have discussed all existing approaches to solve the problem for calculating the min-cut tree of an undirected edge-weighted graph and present a new approximation algorithm for constructing the minimum-cut tree. We discussed Gomory-Hu algorithm. The algorithm proposed by Gomory and Hu has time complexity O(V*time complexity of finding a min s-t cut). We also have discussed Ford-Fulkerson method. Running time of Ford-Fulkerson algorithm is O(ve 2). The asymptotically fastest maximumflow algorithms are based on push-relabel method and have the running time of O(V 3). M. Stoer and F. Wagner have given a simple and compact algorithm for finding the minimum cut of a graph. The algorithm is remarkably simple and has the fastest running time so far the algorithm consists of |V |- 1 identical phases each of which requires O(|e | + |V| log |V|) time yielding an overall running time of O(|V||e | + log |V|). We present a new approximation algorithm for constructing the minimum cut tree. We calculate an upperbound value for each node in the graph. We define the upper bound value of each node as the value of cut which separates this node from rest of the graph and our algorithm runs in O(V 2.logV + V 2.d), where V is the number of vertices in the given graph and d is the degree of the graph. It is a significant improvement over time complexities of existing solutions. However, because of an assumption it does not produce correct result for all sorts of graphs but for the dense graphs success rate is more than 90%. Moreover in the unsuccessful cases, the deviation from actual result is very less (usually for less than 5 % pairs) and for most of the pairs we obtain correct values of max-flow or min-cut. Keywords Undirected edge-weighted graph; min-cut tree; dense graphs; max-flow; min-cut 1.