Algorithms for Finding Maximum Matchings in Bipartite Graphs

In this paper we survey algorithms for finding maximum cardinality and maximum weight matching in a bipartite graph (V, E) with [V] vertices and [E] edges. We discuss the complexity of various algorithms, with an emphasis on algorithms for sparse graphs. We provide a detailed tutorial description of implementations of some promising algorithms, suggest improvements, and provide detailed experimental results on large sparse matrices. The improvements that we suggesst significantly reduce the execution time of the original algorithm for findgin the maximum weight matching in sparse bipartite graphs. One of them leads to an algorithm with a lower expected asymptotic complexity than the current best known worst-case bound of O([V][E]log[V]) if the edge-weights are independent random variables. We also show that if (1) the graph can be partitioned into two parts by a node-separator of size O([V] ), where O< < 1, (2) the number of nodes in the larger of the two partitions does not exceed [V]/c, where c>1, and (3) both partitions of the graph recursively obey conditions (1) and (2), then the maximum-weight bipartite matching problem can be solved in O([V] [E]log[V]) time. This is significant because a mjority of graphs arising in real-world applications lend themselves to such partitioning in O([V]log{V]) time.