Research Article
A New Technique for Finding Min-cut Tree
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 69 - Issue 20 |
| Published: May 2013 |
| Authors: Ashwani Kumar, Surinder Pal Singh, Nitin Arora |
10.5120/12084-9170
|
Ashwani Kumar, Surinder Pal Singh, Nitin Arora . A New Technique for Finding Min-cut Tree. International Journal of Computer Applications. 69, 20 (May 2013), 1-7. DOI=10.5120/12084-9170
@article{ 10.5120/12084-9170,
author = { Ashwani Kumar,Surinder Pal Singh,Nitin Arora },
title = { A New Technique for Finding Min-cut Tree },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 69 },
number = { 20 },
pages = { 1-7 },
doi = { 10.5120/12084-9170 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Ashwani Kumar
%A Surinder Pal Singh
%A Nitin Arora
%T A New Technique for Finding Min-cut Tree%T
%J International Journal of Computer Applications
%V 69
%N 20
%P 1-7
%R 10.5120/12084-9170
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper we propose a new approximation algorithm for calculating the min-cut tree of an undirected edge-weighted graph. Our algorithm runs in O(V2. logV + V2. 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.
References
- Arora N. , Kaushik P. K. and Singh S. P. , "A Survey on Methods for finding Min-Cut Tree". International Journal of Computer Applications (IJCA), Volume 66, No. 23, March 2013, pp. 18-22.
- Stoer M. and Wagner F. "A Simple Min-Cut Algorithm". Journal of the ACM (JACM), Volume 44, No. 4, July 1997, pp. 585-591.
- Brinkmeier M. 2007. "A Simple and Fast Min-Cut Algorithm". Theory of Computing Systems, Volume 41, issue 2, pp. 369-380.
- Gomory R. E. and Hu T. C. December 1961. "Multi-Terminal Network Flows". J. Soc. Indust. Appl. Math, volume 9, No. 4.
- L. R. Ford and D. R. Fulkerson. Maximal Flow through a network. Can. J. Math. , 8:399-404, 1956.
- Hu T. C. 1974. "Optimum Communication Spanning Trees". SIAM J. Computing, volume 3, issue 3.
- Flake G. W. , Tarjan R. E. and Tsioutsiouliklis K. "Graph Clustering and Minimum Cut Trees". Internet Mathematics, volume 1, issue 4, 385-408.
- Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein.
Index Terms
Keywords