Ungarische Methode

Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden, die ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode. Die originale Implementierung hatte eine Komplexität von ${\displaystyle O(n^{4})}$, durch geeignete Datenstrukturen und optimierte Unterroutinen konnte diese auf ${\displaystyle O(n^{3})}$ gesenkt werden.

Die Ungarische Methode wurde 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry entwickelt und von James Munkres 1957, einer Analyse der Laufzeit folgend, verbessert.