Maximum-weight matching

Basic definitions

1. Basic graph definitions
2. Matchings in graphs

Definition

Input:

1. An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
2. A real-valued weight [math]\displaystyle{ c(e) }[/math] for each edge [math]\displaystyle{ e\in E }[/math].

Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \sum_{e\in M'}c(e)\leq\sum_{e\in M}c(e) }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].

Known algorithms

1. The Hungarian method for bipartite graphs

Remarks

1. The maximum-weight matching problem restricted to bipartite graphs is usually called the assignment problem.
2. If the graph is bipartite, [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math], we may assume [math]\displaystyle{ |V_1|=|V_2| }[/math] without loss of generality (just add the missing nodes to the smaller node set). Then the perfect matching of minimum weight can be found as follows:
   1. Let [math]\displaystyle{ C:=\max\{c(e)|e\in E\} }[/math].
   2. For each edge [math]\displaystyle{ e\in E }[/math], set [math]\displaystyle{ c'(e):=C-c(e) }[/math].
   3. Find a maximum-weight matching with respect to [math]\displaystyle{ c' }[/math].