Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching)

From Algorithm Wiki
Revision as of 11:14, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(V)$ auxiliary 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/doi/10.1137/0202019")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Time Complexity

$O((V^{0.5})$E)

Space Complexity

$O(V)$ auxiliary 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/doi/10.1137/0202019

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Hopcroft–Karp_algorithm_(Bipartite_Graph_MCM_Maximum_Cardinality_Matching)&oldid=45253"