Achatz-Kleinschmidt-Paparrizos-Algorithmus

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 $O(n^{3}).$ ^[1]

Der Algorithmus wurde 1991 von Hans Achatz, Peter Kleinschmidt und Konstantinos Paparrizos veröffentlicht.^[2]

Literatur 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

↑ 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.

[1] 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.

[2] 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.

[1]

[2]