public class BipartiteMatching
extends java.lang.Object
Compilation: javac BipartiteMatching.java
Execution: java BipartiteMatching N E
Dependencies: FordFulkerson.java FlowNetwork.java FlowEdge.java
Find a maximum matching in a bipartite graph. Solve by reducing
to maximum flow.
The order of growth of the running time in the worst case is E V
because each augmentation increases the cardinality of the matching
by one.
The Hopcroft-Karp algorithm improves this to E V^1/2 by finding
a maximal set of shortest augmenting paths in each phase.