Planar Bipartite Graph Perfect Matching

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.

Parameters

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

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Klein (section 5)	1997	$O(V^{4/3} \log V)$	$O(V^{4/3})$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table