Bipartite Maximum-Weight Matching (Maximum-Weight Matching)

From Algorithm Wiki
Jump to navigation Jump to search


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.

Related Problems

Generalizations: Maximum-Weight Matching


$n$: number of vertices

$m$: number of edges

$N$: largest weight magnitude

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Hungarian algorithm 1955 $O(n^{4})$ $O(n^{2})$ Exact Deterministic Time
Micali; Vazirani 1980 $O(n^{3} \log n)$ Exact Deterministic Time
Mucha and Sankowski 2004 $O(n^{3})$ Exact Deterministic Time

Time Complexity Graph

Maximum-Weight Matching - Bipartite Maximum-Weight Matching - Time.png