General Graph MCM (Maximum Cardinality Matching)

Description

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.

Related Problems

Subproblem: Bipartite Graph MCM

Related: Planar Bipartite Graph Perfect Matching

Parameters

V: number of vertices

E: number of edges

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Micali and Vazirani	1980	$O(V^{0.5}E)$	$O(V)$		Deterministic	Time & Space
Blum	1990	$O((V^{0.5})$E)	$O(E)$ auxiliary??	Exact	Deterministic	Time
Gabow; Tarjan	1991	$O((V^{0.5})$E)	$O(E)$ auxiliary?	Exact	Deterministic	Time & Space
Mucha, Sankowski (general)	2004	$O(V^{2.376})$	$O(V^2)$??	Exact	Randomized	Time

Time Complexity Graph

Space Complexity Graph

Space-Time Tradeoff Improvements