File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A decomposition theorem for maximum weight bipartite matchings

TitleA decomposition theorem for maximum weight bipartite matchings
Authors
KeywordsAll-cavity matchings
Graph algorithms
Maximum weight matchings
Minimum weight covers
Unfolded graphs
Issue Date2001
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
Siam Journal On Computing, 2001, v. 31 n. 1, p. 18-26 How to Cite?
AbstractLet G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x/ log(x2/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW/k(n, W/N))-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G - {u} for all nodes u in O(W) time. © 2001 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/43656
ISSN
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 2.143
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2007-03-23T04:51:22Z-
dc.date.available2007-03-23T04:51:22Z-
dc.date.issued2001en_HK
dc.identifier.citationSiam Journal On Computing, 2001, v. 31 n. 1, p. 18-26en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43656-
dc.description.abstractLet G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x/ log(x2/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW/k(n, W/N))-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G - {u} for all nodes u in O(W) time. © 2001 Society for Industrial and Applied Mathematics.en_HK
dc.format.extent177697 bytes-
dc.format.extent25600 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rights© 2001 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 31, issue 1, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectAll-cavity matchingsen_HK
dc.subjectGraph algorithmsen_HK
dc.subjectMaximum weight matchingsen_HK
dc.subjectMinimum weight coversen_HK
dc.subjectUnfolded graphsen_HK
dc.titleA decomposition theorem for maximum weight bipartite matchingsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=31&issue=1&spage=18&epage=26&date=2001&atitle=A+Decomposition+Theorem+for+Maximum+Weight+Bipartite+Matchingsen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0097539799361208en_HK
dc.identifier.scopuseid_2-s2.0-0036215968en_HK
dc.identifier.hkuros57730-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036215968&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume31en_HK
dc.identifier.issue1en_HK
dc.identifier.spage18en_HK
dc.identifier.epage26en_HK
dc.identifier.isiWOS:000170396000002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats