An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph

In this article, the authors proposed a new approximation algorithm for calculating the min-cut tree of an undirected edge-weighted graph. Their 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 improvemen...

Full description

Saved in:
Bibliographic Details
Published in:International journal of advanced computer research 2013-06, Vol.3 (2), p.193-193
Main Authors: Bora, Neha, Arora, Swati, Arora, Nitin
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Deviation
Graphs
Mathematical analysis
Mathematical models
Programming languages
Trees
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article, the authors proposed a new approximation algorithm for calculating the min-cut tree of an undirected edge-weighted graph. Their 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. The authors implemented their algorithm in objected oriented 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 deviation from actual result is very less and for most of the pairs they obtain correct values of max-flow.
ISSN:2249-7277
2277-7970