Benchmarking MCM in Complete Graphs

Jump to bottom Edit New page

jaredbeck edited this page Oct 25, 2014 · 2 revisions

MCM in general graphs uses Gabow (1976) which performs in O(n^3).

Note that odd-size graphs take slightly longer than even, perhaps due to blossom expansion.

MCM in Complete Graph is O(v ^ 3)

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