Skip to content

Benchmarking MCM in Complete Bigraphs

Jump to bottom Edit New page
jaredbeck edited this page Nov 3, 2014 · 6 revisions

Maximum Cardinality Matching in Bipartite Graphs currently uses the naïve Augmenting Path algorithm, which performs in O(e * v) where e is the number of edges, and v, the number of vertexes. I know that this is inefficient compared to the Hopcroft-Karp algorithm which performs in O(e * sqrt(v)) in the worst case.

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