Hopcroft-Karp algorithm
Encyclopedia : H : HO : HOP : Hopcroft-Karp algorithm
The Hopcroft-Karp algorithm finds maximum cardinality matchings in bipartite graphs in [O(\sqrt E)] time.
Algorithm
- Input: Bipartite graph [G(V=L \cup R, E)]
- Output: Matching [M \subseteq E]
- [M \leftarrow \empty]
- repeat
- : [\mathcal P \leftarrow \] maximum set of vertex-disjoint shortest augmenting paths
- : [M \leftarrow M \oplus (P_1 \cup P_2 \cup \dots \cup P_k)]
- until [\mathcal P = \empty]
References
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.