Bipartite Maximum-Weight Matching

In computer science, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. Here, the graph must be bipartite.

Parameters

$n$ : number of vertices
$m$ : number of edges
$N$ : largest weight magnitude

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Fredman-Tarjan (Edmonds-Karp-based)	1984	O(mn+n^2log(n))	O(n^2)
Johnson (Edmonds-Karp-based)	1975	O(mn*log(n)/log(2+m/n))	O(n^2)
Edmonds-Karp	1972	$O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^3)$	O(n^2)
Hungarian algorithm	1955	$O(n^4)$	$O(n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms