Maximum weight matching

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Maximum weight matching" – news · newspapers · books · scholar · JSTOR (April 2024)

In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized.

A special case of the maximum weight matching problem is the assignment problem, in which the graph is a bipartite graph and the matching must have cardinality equal to that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same.