General Graph MCM (Maximum Cardinality Matching)

From Algorithm Wiki
Revision as of 09:07, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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


$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)$?? Exact Deterministic Time
Gabow; Tarjan 1991 $O((V^{0.5})$E) $O(E)$? Exact Deterministic Time & Space
Mucha, Sankowski (general) 2004 $O(V^{2.{37}6})$ $O(V^{2})$?? Exact Randomized Time

Time Complexity Graph

Maximum Cardinality Matching - General Graph MCM - Time.png