Perfect matchings in o( n log n ) time in regular bipartite graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna · 2010
In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m√n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to ~ O(min m, n2.5/d) and then to ~O(min {m, n2/d\}).