Computer Science

Seminar 9/30/09: Improving ADJMAT, Corey Oliver

Applications for which bipartite matching is useful, in particular finding perfect matchings are numerous. Heuristics have been put forward by Rakesh Verma to decrease complexity associated with determining whether a given graph is a viable candidate for a perfect matching. This can potentially lessen the overall cost of finding perfect matchings for a given set of graphs.

A software framework called ADJMAT has been designed around the aforementioned heuristics. I will discuss implementation techniques and optimizations utilized to increase the efficiency of this framework thus allowing Verma’s heuristics to be more easily assessed on their merit and substance as opposed to being bounded by limitations of the framework.

Sources: J. Hopcroft and R. Karp.  “An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.” SIAM Journal on Computing, 2(4):225–231, 1973.
R. M. Verma and J. Wiedrick. “Fast filtering heuristics for perfect bipartite matchings.” 2008.