We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A New Technique for Finding Min-cut Tree

by Ashwani Kumar, Surinder Pal Singh, Nitin Arora
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 69 - Number 20
Year of Publication: 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 },
issue_date = { May 2013 },
volume = { 69 },
number = { 20 },
month = { May },
year = { 2013 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume69/number20/12084-9170/ },
doi = { 10.5120/12084-9170 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:30:45.223633+05:30
%A Ashwani Kumar
%A Surinder Pal Singh
%A Nitin Arora
%T A New Technique for Finding Min-cut Tree
%J International Journal of Computer Applications
%@ 0975-8887
%V 69
%N 20
%P 1-7
%D 2013
%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
  1. 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.
  2. Stoer M. and Wagner F. "A Simple Min-Cut Algorithm". Journal of the ACM (JACM), Volume 44, No. 4, July 1997, pp. 585-591.
  3. Brinkmeier M. 2007. "A Simple and Fast Min-Cut Algorithm". Theory of Computing Systems, Volume 41, issue 2, pp. 369-380.
  4. Gomory R. E. and Hu T. C. December 1961. "Multi-Terminal Network Flows". J. Soc. Indust. Appl. Math, volume 9, No. 4.
  5. L. R. Ford and D. R. Fulkerson. Maximal Flow through a network. Can. J. Math. , 8:399-404, 1956.
  6. Hu T. C. 1974. "Optimum Communication Spanning Trees". SIAM J. Computing, volume 3, issue 3.
  7. Flake G. W. , Tarjan R. E. and Tsioutsiouliklis K. "Graph Clustering and Minimum Cut Trees". Internet Mathematics, volume 1, issue 4, 385-408.
  8. Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein.
Index Terms

Computer Science
Information Sciences

Keywords

Undirected edge-weighted graph min-cut tree dense graphs max-flow min-cut

Powered by PhDFocusTM