General 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 can be any general graph.

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Mucha, Sankowski (general)	2004	$O(V^{\omega})$	$O(V^2)$
Gabow; Tarjan	1991	$O(V^{0.5} E)$	$O(E)$
Blum	1990	$O(V^{0.5} E)$	$O(E)$
Micali; Vazirani	1980	$O(E \sqrt{V})$	$O(E)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms