Maximum-weight matching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
Line 8: Line 8:
'''Input:'''
'''Input:'''
# An undirected graph <math>G=(V,E)</math>.
# An undirected graph <math>G=(V,E)</math>.
# A nonnegative '''weight''' <math>c(e)</math> for each edge <math>e\in E</math>.
# A strictly positive '''weight''' <math>c(e)</math> for each edge <math>e\in E</math>.


'''Output:'''
'''Output:'''

Latest revision as of 17:37, 6 December 2014

Basic definitions

  1. Basic graph definitions
  2. Matchings in graphs

Definition

Input:

  1. An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
  2. 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

  1. The Hungarian method for complete 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] and [math]\displaystyle{ |V_1|=|V_2| }[/math], 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].
  3. 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:
    1. [math]\displaystyle{ c(\{v,w\}):=0 }[/math] if a maximum-weight matching is to be computed.
    2. [math]\displaystyle{ c(\{v,w\}) }[/math] sufficiently large if a minimum-weight perfect matching is to be computed.