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_v }[/math] for each node [math]\displaystyle{ v\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].