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 is unrestricted; i.e. can be any general graph.

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms


Gabow	1990	O(mn+n^2log(n))	O(m)
Gabow, Galil, Spencer	1989	O(mnlog(log(log(n)/log(2+m/n))) + n^2log(n))
Galil, Micali, Gabow	1982	O(mn*log(n))
Gabow	1974	O(n^3)
Edmonds	1965	$O(mn^2)$	$O(mn^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms