A simple matching algorithm for regular bipartite graphs. (Q1853135)

We consider the perfect matching problem for a \(\Delta\)-regular bipartite graph with \(n\) vertices and \(m\) edges, i.e., \(\frac12n\Delta=m\), and present a new \(O(m+n\log n\log\Delta)\) algorithm. Cole and Rizzi, respectively, gave algorithms of the same complexity as ours, Schrijver also devised an \(O(m\Delta)\) algorithm, and the best existing algorithm is Cole, Ost, and Schirra's \(O(m)\) algorithm. Extending Gabow's perfect matching algorithm for \(2^{t}\)-regular bipartite graph with a positive integer \(t\) and using Cole and Hopcroft's edge-sparsification technique, we show another approach to the perfect matching problem, which results in a simple algorithm that employs no sophisticated data structure such as dynamic tree and splay tree.