Planar Bipartite Graph Perfect Matching (Maximum Cardinality Matching)

From Algorithm Wiki
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 is a planar bipartite graph.

Related Problems

Generalizations: Bipartite Graph MCM

Related: General Graph MCM


$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
Klein (section 5) 1997 $O(V^{({4}/{3})$} logV) $O(V^{({4}/{3})$})? Exact Deterministic Time

Time Complexity Graph

Maximum Cardinality Matching - Planar Bipartite Graph Perfect Matching - Time.png