Achatz-Kleinschmidt-Paparrizos-Algorithmus

aus Wikipedia, der freien Enzyklopädie
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]

  • 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]
  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.