Editorial/Data Protection
Bipartite Matching

The functions that yield bipartite matchings make use of four algorithms:

Algorithm   Mode of Operation
hungarian method primal-dual optimization
network flow maximum flow at minimum cost in the corresponding 0-1 network
WorstAlternativeNext heuristic
greedy use first applicable edge

Implemented are the following functions:

Function   Short Description
MinimumWeightBipartite-
 PerfectMatching
perfect matching at minimum cost/weight in a bipartite graph

The facing column contains an example for the function.

Graph in Matrixform

{21., {{1, 3}, {2, 1}, {3, 5}, {4, 2}, {5, 4}}}

Plot bipartites Matching

Editorial/Data Protection • page checked on Nov. 28th 2005