Maximum-weight matching: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Basic definitions == # Basic graph definitions # Matchings in graphs == Definition == '''Input:''' # An undirected graph <math>G=(V,E)</math>. # A '''weight''' <...") |
|||
| Line 8: | Line 8: | ||
'''Input:''' | '''Input:''' | ||
# An undirected graph <math>G=(V,E)</math>. | # An undirected graph <math>G=(V,E)</math>. | ||
# A '''weight''' <math>w(e)</math> for each edge <math>e\in E</math>. | # A real-valued '''weight''' <math>w(e)</math> for each edge <math>e\in E</math>. | ||
'''Output:''' | '''Output:''' | ||
A matching <math>M</math> in <math>G</math> such that <math>\sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e)</math> for any other matching <math>M'</math> in <math>G</math>. | A matching <math>M</math> in <math>G</math> such that <math>\sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e)</math> for any other matching <math>M'</math> in <math>G</math>. | ||
Revision as of 10:16, 21 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].