Hungarian method: Difference between revisions
Jump to navigation
Jump to search
| Line 20: | Line 20: | ||
Initialize all <math>x</math> and <math>y</math> values such that the invariant is fulfilled, for example: | Initialize all <math>x</math> and <math>y</math> values such that the invariant is fulfilled, for example: | ||
# <math>x(v):=\max\{c(\{v,w\})|w\in V_2\}</math> for all <math>v\in | # <math>x(v):=\max\{c(\{v,w\})|w\in V_2\}</math> for all <math>v\in V_1</math>. | ||
# <math>y(w):=0</math> for all <math>w\in V:2</math>, | # <math>y(w):=0</math> for all <math>w\in V:2</math>, | ||
== Induction step == | == Induction step == | ||
Revision as of 18:52, 22 November 2014
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:
- A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
- A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].
Invariant:
- 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:
- [math]\displaystyle{ x(v):=\max\{c(\{v,w\})|w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V_1 }[/math].
- [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V:2 }[/math],