ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph

Journal: International Journal of Advanced Computer Research (IJACR) (Vol.3, No. 10)

Publication Date:

Authors : ; ; ;

Page : 193-199

Keywords : Approximation Algorithm; Max - Flow; Min - Cut; Object Oriented Programming.;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

In this paper we proposed a new approximation algorithm for calculating the min - cut tree of an undirected edge - weighted gra ph. 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. We implemented our algorithm in objected orie nted programming language and checked for many input cases. 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 deviati on from actual result is very less and for most of the pairs we obtain correct values of max - flow.

Last modified: 2014-12-17 22:00:26