Maximum-weight matching: Difference between revisions
Jump to navigation
Jump to search
| Line 21: | Line 21: | ||
# The maximum-weight matching problem restricted to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] is usually called the '''assignment problem'''. | # The maximum-weight matching problem restricted to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] is usually called the '''assignment problem'''. | ||
# If the graph is bipartite, <math>G=(V_1\dot\cup V_2,E)</math>, we may assume <math>|V_1|=|V_2|</math> without loss of generality (just add the missing nodes to the smaller node set). Then the [[Matchings in graphs|perfect matching]] of ''minimum'' weight can be found as follows: | # If the graph is bipartite, <math>G=(V_1\dot\cup V_2,E)</math>, we may assume <math>|V_1|=|V_2|</math> without loss of generality (just add the missing nodes to the smaller node set). Then the [[Matchings in graphs|perfect matching]] of ''minimum'' weight can be found as follows: | ||
## Let <math>C:=\max\{c(e)|e\in E | ## Let <math>C:=\max\{c(e)|e\in E\}</math>. | ||
## For each edge <math>e\in E</math>, set <mathg>c'(e):=C-c(e)</math>. | ## For each edge <math>e\in E</math>, set <mathg>c'(e):=C-c(e)</math>. | ||
## Find a ''maximum''-weight matching with respect to <math>c'</math>. | ## Find a ''maximum''-weight matching with respect to <math>c'</math>. | ||
Revision as of 18:23, 22 November 2014
Basic definitions
Definition
Input:
- An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
- 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
- The Hungarian method for bipartite graphs
Remarks
- The maximum-weight matching problem restricted to bipartite graphs is usually called the assignment problem.
- 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:
- Let [math]\displaystyle{ C:=\max\{c(e)|e\in E\} }[/math].
- For each edge [math]\displaystyle{ e\in E }[/math], set <mathg>c'(e):=C-c(e)</math>.
- Find a maximum-weight matching with respect to [math]\displaystyle{ c' }[/math].