Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching)
Jump to navigation
Jump to search
Time Complexity
$O((V^{0.5})$E)
Space Complexity
$O(V)$ words
(maximal set of vertex-disjoint shortest augmenting paths uses O(V) space to store, taking symmetric difference also uses O(V) space)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1973
Reference
https://epubs-siam-org.ezproxy.canberra.edu.au/doi/10.1137/0202019