A Competitive Strong Spanning Tree Algorithm for the Maximum Bipartite Matching Problem
Jaime González, Osvaldo Landaeta · SIAM Journal on Discrete Mathematics · 1995
The new characterization for maximum matching in bipartite graphs given by Balinski and González is based on “strong spanning trees” and is independent on the classical notion of augmenting path. However, the algorithm that they derived runs in $0( | V | | E | )$ time for bipartite graphs with $| V |$ nodes and $| E |$ edges, and so it is not competitive with the $0( \sqrt {| V |} | E | )$ algorithm of Hopcroft and Karp. In this paper we prove that the basic results given by Hopcroft and Karp can also be obtained using the new characterization, allowing us to develop a competitive algorithm.