The Matching Problem deals with the search of a relation between two different sets. A classic example is the so-called ‘Marriage Problem’, in which a set of women and a set of men are given. In addition, we have information on who would accept whom as a potential life partner. A matching then is a set of couples that are ‘compatible’ with one another. The Weighted Matching Problem is a more general case that gives preferences to different relations in order to obtain the best allocation possible. This problem can be solved by the Hungarian Method.
logo for the category 'Blossom Algorithm'
Blossom Algorithm

The Blossom Algorithm computes a maximal matching in an arbitrary graph (in contrast to the Hopcroft-Karp algorithm which requires a bipartite graph).

logo for the category 'Hopcroft-Karp Algorithm'
Hopcroft-Karp Algorithm

The Hopcroft-Karp Algorithm computes for two given sets with possible assignments a maximal relation.

logo for the category 'Hungarian Method'
Hungarian Method

The Hungarian Method determines for two given sets with weighted assignments a maximal (with respect to the weights) relation.