Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs
Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs
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\sqrt{n})$. In regular bipartite graphs, however, a matching is known to …