In this paper we survey algorithms for finding the maximum cardinality and the maximum weight matching in a bipartite graph. We discuss the complexity of various algorithms for these problems, with an emphasis on algorithms for sparse graphs. We provide a detailed tutorial description of implementations of some promising algorithms, suggest improvements, and provide an experimental comparison of our code with other well-known codes on large sparse matrices. The improvements that we suggest significantly reduce the execution time of the original algorithm for finding the maximum weight matching in sparse bipartite graphs with the best-known strongly polynomial worst-case time complexity.
By: Anshul Gupta, Lexing Ying (NYU)
Published in: RC21576 in 1999
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .