Maximum-weight matching: Difference between revisions
Jump to navigation
Jump to search
(→Remark) |
|||
| (10 intermediate revisions by the same user not shown) | |||
| Line 8: | Line 8: | ||
'''Input:''' | '''Input:''' | ||
# An undirected graph <math>G=(V,E)</math>. | # An undirected graph <math>G=(V,E)</math>. | ||
# A | # A strictly positive '''weight''' <math>c(e)</math> for each edge <math>e\in E</math>. | ||
'''Output:''' | '''Output:''' | ||
| Line 15: | Line 15: | ||
== Known algorithms == | == Known algorithms == | ||
# The [[Hungarian method]] for [[Basic graph definitions#Bipartite and k-partite graphs|bipartite | # The [[Hungarian method]] for [[Basic graph definitions#Complete graphs|complete]] [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]] graphs. | ||
== Remarks == | == Remarks == | ||
# 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> | # If the graph is bipartite, <math>G=(V_1\dot\cup V_2,E)</math> and <math>|V_1|=|V_2|</math>, the [[Matchings in graphs|perfect matching]] of ''minimum'' weight can be found as follows: | ||
## Let <math>C:=\max\{c(e)|e\in E</math>. | ## Let <math>C:=\max\{c(e)|e\in E\}</math>. | ||
## For each edge <math>e\in E</math>, set < | ## For each edge <math>e\in E</math>, set <math>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>. | ||
# If <math>|V_1|\neq|V_2|</math>, say <math>|V_1|<|V_2|</math>, we may simply add as many as <math>|V_2|-|V_1|</math> nodes to <math>V_1</math> and for each new node <math>v</math> one edge <math>\{v,w\}</math> to every node <math>w\in V_2</math> with: | |||
## <math>c(\{v,w\}):=0</math> if a maximum-weight matching is to be computed. | |||
## <math>c(\{v,w\})</math> sufficiently large if a minimum-weight perfect matching is to be computed. | |||
Latest revision as of 17:37, 6 December 2014
Basic definitions
Definition
Input:
- An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
- A strictly positive 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 complete 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] and [math]\displaystyle{ |V_1|=|V_2| }[/math], 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 [math]\displaystyle{ c'(e):=C-c(e) }[/math].
- Find a maximum-weight matching with respect to [math]\displaystyle{ c' }[/math].
- If [math]\displaystyle{ |V_1|\neq|V_2| }[/math], say [math]\displaystyle{ |V_1|\lt |V_2| }[/math], we may simply add as many as [math]\displaystyle{ |V_2|-|V_1| }[/math] nodes to [math]\displaystyle{ V_1 }[/math] and for each new node [math]\displaystyle{ v }[/math] one edge [math]\displaystyle{ \{v,w\} }[/math] to every node [math]\displaystyle{ w\in V_2 }[/math] with:
- [math]\displaystyle{ c(\{v,w\}):=0 }[/math] if a maximum-weight matching is to be computed.
- [math]\displaystyle{ c(\{v,w\}) }[/math] sufficiently large if a minimum-weight perfect matching is to be computed.