Skip to content

Benchmarking MCM in Complete Bigraphs

Jump to bottom Edit New page
jaredbeck edited this page Oct 25, 2014 · 6 revisions

Maximum Cardinality Matching in Bipartite Graphs currently uses the Augmenting Path algorithm, which performs in O(e * v) where e is the number of edges, and v, the number of vertexes.

Currently, MCM on a complete 500 vertex bigraph takes about 7 seconds. I'm not satisfied with this, and I know that the algorithm I'm using is inefficient compared to the Hopcroft-Karp algorithm which performs in O(e * sqrt(v)) in the worst case.

I'm using the naïve Augmenting Path algorithm, which I expected to perform in O(e * v). Here are my results:

MCM in Complete Bigraph is O(e * v)

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

Add a custom footer
Add a custom sidebar
Clone this wiki locally