Hungarian method

Abstract view

Algorithmic problem: Maximum-weight matching in [Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math].

Type of algorithm: loop.

Auxiliary data:

1. A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
2. A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].

Invariant:

1. For each edge [math]\displaystyle{ e=\{v,w\}\in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)\leq x(v)+y(w) }[/math].

Variant:

Break condition: For each edge [math]\displaystyle{ e=\{v,w\} in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].

Induction basis

Initialize all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] values such that the invariant is fulfilled, for example:

1. [math]\displaystyle{ x(v):=\max\{c(\{v,w\}\w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V }[/math].
2. [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V:2 }[/math],