Benchmarking MWM in Complete Bigraphs

Uses the Augmenting Path algorithm from Maximum Cardinality Matching, with the "scaling" approach described by Gabow (1983) and Galil (1986).

The bigraphs used in this benchmark are:

1. Complete - Each vertex in U has an edge to each vertex in V
2. Weighted - Each edge has a different, consecutive integer weight
3. "Balanced"

• In an even bigraph, U and V have the same number of vertexes.
• In an odd bigraph, U has one more than V.
• 0 <= abs(U - V) <= 1

These attributes produce the "worst case" bigraph, i.e. the most expensive over which to produce a complete matching.

Plot generated using gnuplot. Benchmark scripts and data may be found in /benchmark.