Achatz-Kleinschmidt-Paparrizos-Algorithmus
Zur Navigation springen
Zur Suche springen
Der Achatz-Kleinschmidt-Paparrizos-Algorithmus, auch AKP-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der linearen Optimierung formuliert werden. Der AKP-Algorithmus ist besonders für dünne Graphen geeignet. Seine Komplexität des Algorithmus beträgt [1]
Der Algorithmus wurde 1991 von Hans Achatz, Peter Kleinschmidt und Konstantinos Paparrizos veröffentlicht.[2]
Literatur
[Bearbeiten | Quelltext bearbeiten]- H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 1–11.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 5.
- ↑ H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 1.