Computer Algorithms II Lecture Notes

20 November 2008 • Traveling, Flowing, and Matching

Hopcroft and Karp shows that maximal matching in bipartite graphs using maximal flow has O(V^0.5E) behavior (Section 6.4, Maximal Matching in Bipartite Graphs, Graph Algorithms by Shimon Even, Computer Science Press, 1979).

This page last modified on 24 January 2006.