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!
cited_by
cites
container_end_page 193
container_issue 2
container_start_page 193
container_title International journal of advanced computer research
container_volume 3
creator Bora, Neha
Arora, Swati
Arora, Nitin
description 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.
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_miscellaneous_1671539918</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>3106672931</sourcerecordid><originalsourceid>FETCH-LOGICAL-p618-20f651663b2b2eaa91e888546ec78b4f7926d0e955e92233e93d167d5ce9b6983</originalsourceid><addsrcrecordid>eNpdjktLxDAcxIsouKz7HQJevBTyfhxrWVeh4mXvJW3_3UbSh0kKfny76MnTDDM_hrnJdpQqlSuj8O3Vc5OrLbjPDjG6BnOuOKYa77KqmNCx713rYEqo8Jc5uDSMqJ8DKq1vV2-Tmy7o3X67cR3Rs1tsSC4BGm1qh2vlJmTRKdhleMjueusjHP50n51fjufyNa8-Tm9lUeWLJDqnuJeCSMka2lCw1hDQWgsuoVW64b0yVHYYjBBgKGUMDOuIVJ1owTTSaLbPnn5nlzB_rRBTPbrYgvd2gnmN9QYTwYwhV_TxH_o5r2HaztWEc04ElZKzH3mwV5c</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1444152664</pqid></control><display><type>article</type><title>An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph</title><source>Publicly Available Content (ProQuest)</source><creator>Bora, Neha ; Arora, Swati ; Arora, Nitin</creator><creatorcontrib>Bora, Neha ; Arora, Swati ; Arora, Nitin</creatorcontrib><description>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.</description><identifier>ISSN: 2249-7277</identifier><identifier>EISSN: 2277-7970</identifier><language>eng</language><publisher>Bhopal: Accent Social and Welfare Society</publisher><subject>Algorithms ; Approximation ; Deviation ; Graphs ; Mathematical analysis ; Mathematical models ; Programming languages ; Trees</subject><ispartof>International journal of advanced computer research, 2013-06, Vol.3 (2), p.193-193</ispartof><rights>Copyright International Journal of Advanced Computer Research Jun 2013</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1444152664/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1444152664?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,776,780,25731,36989,36990,44566,75096</link.rule.ids></links><search><creatorcontrib>Bora, Neha</creatorcontrib><creatorcontrib>Arora, Swati</creatorcontrib><creatorcontrib>Arora, Nitin</creatorcontrib><title>An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph</title><title>International journal of advanced computer research</title><description>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.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Deviation</subject><subject>Graphs</subject><subject>Mathematical analysis</subject><subject>Mathematical models</subject><subject>Programming languages</subject><subject>Trees</subject><issn>2249-7277</issn><issn>2277-7970</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2013</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNpdjktLxDAcxIsouKz7HQJevBTyfhxrWVeh4mXvJW3_3UbSh0kKfny76MnTDDM_hrnJdpQqlSuj8O3Vc5OrLbjPDjG6BnOuOKYa77KqmNCx713rYEqo8Jc5uDSMqJ8DKq1vV2-Tmy7o3X67cR3Rs1tsSC4BGm1qh2vlJmTRKdhleMjueusjHP50n51fjufyNa8-Tm9lUeWLJDqnuJeCSMka2lCw1hDQWgsuoVW64b0yVHYYjBBgKGUMDOuIVJ1owTTSaLbPnn5nlzB_rRBTPbrYgvd2gnmN9QYTwYwhV_TxH_o5r2HaztWEc04ElZKzH3mwV5c</recordid><startdate>20130601</startdate><enddate>20130601</enddate><creator>Bora, Neha</creator><creator>Arora, Swati</creator><creator>Arora, Nitin</creator><general>Accent Social and Welfare Society</general><scope>3V.</scope><scope>7SC</scope><scope>7XB</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>P5Z</scope><scope>P62</scope><scope>PHGZM</scope><scope>PHGZT</scope><scope>PIMPY</scope><scope>PKEHL</scope><scope>PQEST</scope><scope>PQGLB</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>Q9U</scope></search><sort><creationdate>20130601</creationdate><title>An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph</title><author>Bora, Neha ; Arora, Swati ; Arora, Nitin</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-p618-20f651663b2b2eaa91e888546ec78b4f7926d0e955e92233e93d167d5ce9b6983</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2013</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Deviation</topic><topic>Graphs</topic><topic>Mathematical analysis</topic><topic>Mathematical models</topic><topic>Programming languages</topic><topic>Trees</topic><toplevel>online_resources</toplevel><creatorcontrib>Bora, Neha</creatorcontrib><creatorcontrib>Arora, Swati</creatorcontrib><creatorcontrib>Arora, Nitin</creatorcontrib><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central (New)</collection><collection>ProQuest One Academic (New)</collection><collection>Publicly Available Content (ProQuest)</collection><collection>ProQuest One Academic Middle East (New)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Applied &amp; Life Sciences</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest Central Basic</collection><jtitle>International journal of advanced computer research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bora, Neha</au><au>Arora, Swati</au><au>Arora, Nitin</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph</atitle><jtitle>International journal of advanced computer research</jtitle><date>2013-06-01</date><risdate>2013</risdate><volume>3</volume><issue>2</issue><spage>193</spage><epage>193</epage><pages>193-193</pages><issn>2249-7277</issn><eissn>2277-7970</eissn><abstract>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.</abstract><cop>Bhopal</cop><pub>Accent Social and Welfare Society</pub><tpages>1</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2249-7277
ispartof International journal of advanced computer research, 2013-06, Vol.3 (2), p.193-193
issn 2249-7277
2277-7970
language eng
recordid cdi_proquest_miscellaneous_1671539918
source Publicly Available Content (ProQuest)
subjects Algorithms
Approximation
Deviation
Graphs
Mathematical analysis
Mathematical models
Programming languages
Trees
title An Efficient Algorithm for Calculating Maximum Bipartite matching in a Graph
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-24T02%3A04%3A34IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=An%20Efficient%20Algorithm%20for%20Calculating%20Maximum%20Bipartite%20matching%20in%20a%20Graph&rft.jtitle=International%20journal%20of%20advanced%20computer%20research&rft.au=Bora,%20Neha&rft.date=2013-06-01&rft.volume=3&rft.issue=2&rft.spage=193&rft.epage=193&rft.pages=193-193&rft.issn=2249-7277&rft.eissn=2277-7970&rft_id=info:doi/&rft_dat=%3Cproquest%3E3106672931%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-p618-20f651663b2b2eaa91e888546ec78b4f7926d0e955e92233e93d167d5ce9b6983%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1444152664&rft_id=info:pmid/&rfr_iscdi=true