the Hopcroft-Karp algorithm
/ HOP-croft KARP /
The plain way to find a maximum bipartite matching is to keep finding one augmenting (alternating) path at a time and flip it, which can take up to V augmentations each costing a search. Hopcroft-Karp speeds this up with the same insight that powers Dinic: instead of one path per round, find and flip a whole maximal batch of shortest augmenting paths at once. Batching slashes the number of rounds from V to about sqrt(V).
Each phase does two things. First, a BFS from all unmatched left vertices computes the length of the shortest augmenting path and layers the graph by distance. Second, a DFS finds a maximal set of vertex-disjoint shortest augmenting paths and augments along all of them simultaneously. The key analysis: after each phase the length of the shortest augmenting path strictly increases, and one can show that after O(sqrt(V)) phases the remaining matching is within sqrt(V) of maximum, so only O(sqrt(V)) more single augmentations are needed — O(sqrt(V)) phases total. Each phase is a BFS plus DFS over the whole graph, costing O(E), so the algorithm runs in O(E * sqrt(V)). This is exactly Dinic's bound specialized to unit-capacity (matching) networks, which is no coincidence: Hopcroft-Karp is Dinic in matching clothing.
Hopcroft-Karp is the standard fast algorithm for maximum bipartite matching, beating the naive O(V * E) augmenting-path approach and Edmonds-Karp's general O(V * E^2) by exploiting the unit-capacity structure. It is the right tool when matchings are large and the graph is big — assignment problems, bipartite covering, scheduling. Two honest notes: the O(E * sqrt(V)) bound is for unweighted bipartite matching only (for minimum-cost or maximum-weight matching you need the Hungarian algorithm or min-cost flow), and for general non-bipartite graphs the analogous fast algorithm is Micali-Vazirani, not Hopcroft-Karp.
On a bipartite graph with V = 10000 vertices, a naive augmenting-path matcher might do up to ~5000 augmentation searches; Hopcroft-Karp finishes in about sqrt(10000) = 100 phases, each a single linear scan of the edges. The batching of shortest augmenting paths is the entire win.
Batch all shortest augmenting paths per phase, and the phase count drops to O(sqrt(V)) — Dinic's idea, specialized to matching.
Hopcroft-Karp solves unweighted bipartite matching only. For weighted/min-cost assignment use the Hungarian algorithm or min-cost flow; for general non-bipartite graphs the fast analogue is Micali-Vazirani, not this algorithm.