Maximum-weight matching: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 15: | Line 15: | ||
== Known algorithms == | == Known algorithms == | ||
# The [[Hungarian method]] for [Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] | # The [[Hungarian method]] for [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] | ||
== Remark == | == Remark == | ||
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'''. | ||
Revision as of 18:02, 22 November 2014
Basic definitions
Definition
Input:
- An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
- A real-valued weight [math]\displaystyle{ w(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'}w(e)\leq\sum_{e\in M}w(e) }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].
Known algorithms
- The Hungarian method for bipartite graphs
Remark
The maximum-weight matching problem restricted to bipartite graphs is usually called the assignment problem.