Academic Journals Database
Disseminating quality controlled scientific knowledge

An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph

Author(s): Neha Bo ra | Swati Arora | Nitin Arora

Journal: International Journal of Advanced Computer Research
ISSN 2249-7277

Volume: 3;
Issue: 10;
Start page: 193;
Date: 2013;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

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

n this paper we proposed a new approximationalgorithm for calculating the min-cut tree of anundirected edge-weighted graph. Our algorithmruns in O (V2.logV + V2.d), where V is the numberof vertices in the given graph and d is the degree ofthe graph. It is a significant improvement over timecomplexities of existing solutions. We implementedour algorithm in objected oriented programminglanguage and checked for many input cases.However, because of an assumption it does notproduce correct result for all sorts of graphs but forthe dense graphs success rate is more than 90%.Moreover in the unsuccessful cases, the deviationfrom actual result is very less and for most of thepairs we obtain correct values of max-flow
Affiliate Program      Why do you need a reservation system?