Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm finds a maximum cardinality matching in a bipartite graph by repeatedly finding a maximal set of shortest augmenting paths using a breadth-first search phase followed by a depth-first search phase that augments the matching along each found path, increasing the matching size in rounds until no augmenting path remains. John Hopcroft and Richard Karp published it in 1973, and it runs in O(E times the square root of V) time, an improvement over the O(VE) time of earlier augmenting path methods for bipartite matching. It remains the standard efficient algorithm for bipartite maximum matching problems such as job assignment.