Bipartite Graph MCM

The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite.

Parameters

$V$ : number of vertices
$E$ : number of edges

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Madry's algorithm	2013	$O(E^{10/7} \text{polylog}(V))$	$O(V + E)$
Chandran and Hochbaum	2011	$O(\min(Vk, E)+\sqrt{k}\min(k^2, E))$	$O(E)$
Hopcroft–Karp algorithm	1973	$O(V^{0.5} E)$	$O(V)$
Ford–Fulkerson algorithm	1956	$O(VE)$	$O(E)$

Reductions Table

Displaying 1 of 1 reductions

			See more
Online Vector-Matrix-Vector Multiplication	Bipartite Graph MCM	2016

Other relevant algorithms

Insuffient Data to display table