Advanced Programming I Lecture Notes

28 March 2006 • 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.