CFP last date
22 April 2024
Reseach Article

Novel Approximation Algorithm for Calculating Maximum Flow in a Graph

by Madhu Lakshmi, Pradeep Kumar Kaushik, Nitin Arora
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 74 - Number 3
Year of Publication: 2013
Authors: Madhu Lakshmi, Pradeep Kumar Kaushik, Nitin Arora
10.5120/12864-9693

Madhu Lakshmi, Pradeep Kumar Kaushik, Nitin Arora . Novel Approximation Algorithm for Calculating Maximum Flow in a Graph. International Journal of Computer Applications. 74, 3 ( July 2013), 14-23. DOI=10.5120/12864-9693

@article{ 10.5120/12864-9693,
author = { Madhu Lakshmi, Pradeep Kumar Kaushik, Nitin Arora },
title = { Novel Approximation Algorithm for Calculating Maximum Flow in a Graph },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 74 },
number = { 3 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 14-23 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume74/number3/12864-9693/ },
doi = { 10.5120/12864-9693 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:41:14.626122+05:30
%A Madhu Lakshmi
%A Pradeep Kumar Kaushik
%A Nitin Arora
%T Novel Approximation Algorithm for Calculating Maximum Flow in a Graph
%J International Journal of Computer Applications
%@ 0975-8887
%V 74
%N 3
%P 14-23
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper a new approximation algorithm for calculating the min-cut tree of an undirected edge-weighted graph has been proposed. This algorithm runs in , 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 sort 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 and for most of the pairs we obtain correct values of max-flow or min-cut. This algorithm is implemented in JAVA language and checked for many input cases.

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. Kumar A. , Singh S. P. and Arora N. , "A New Technique for Finding Min-Cut Tree". International Journal of Computer Applications (IJCA), Volume 69, No. 20, May 2013, pp. 1-7.
  3. Stoer M. and Wagner F. 1997. "A Simple Min-Cut Algorithm". Journal of the ACM (JACM), volume 44, issue 4, 585-591.
  4. Brinkmeier M. 2007. "A Simple and Fast Min-Cut Algorithm". Theory of Computing Systems, volume 41, issue 2, 369-380.
  5. Hu T. C. 1974. "Optimum Communication Spanning Trees". SIAM J. Computing, volume 3, issue 3.
  6. Flake G. W. , Tarjan R. E. and Tsioutsiouliklis K. Graph Clustering and Minimum Cut Trees. Internet Mathematics, volume 1, issue 4, 385-408.
  7. Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein.
  8. Gomory R. E. and Hu T. C. December 1961. Multi-Terminal Network Flows. J. Soc. Indust. Appl. Math, volume 9, No. 4
Index Terms

Computer Science
Information Sciences

Keywords

Maximum Flow approximation Algorithm complexity min-cut tree