edu.princeton.cs.algorithms

Class BipartiteMatching

java.lang.Object

edu.princeton.cs.algorithms.BipartiteMatching

public class BipartiteMatching
extends 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.

Constructor Summary

Constructors

Constructor and Description
BipartiteMatching()

Method Summary

Methods

Modifier and Type	Method and Description
static void	main(String[] args)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BipartiteMatching

public BipartiteMatching()

Method Detail

main

public static void main(String[] args)