Schnellere Approximationsalgorithmen zur Partiell-Dynamischen Berechnung Kürzester Wege

Abstract

Ein Algorithmus gilt als dynamisch wenn seine Eingabe mit der Zeit immer wieder Änderungen unterworfen ist und er deshalb das Ergebnis seiner Berechnungen regelmäßig aktualisiert. Das Hauptziel ist es, schneller zu sein als ein naiver Algorithmus, der das Ergebnis nach jeder Änderung von Grund auf neu berechnet. Für dynamische Probleme auf Graphen bestehen die Änderungen in der Regel aus Einfügungen und Löschungen von Kanten. In dieser Arbeit konzentrieren wir uns auf partiell-dynamische Algorithmen, die nur eine Art von Änderungen erlauben; entweder ausschließ- lich Einfügungen (inkrementeller Algorithmus) oder ausschließlich Löschungen (dekrementeller Algorithmus). Wir entwickeln schnellere, partiell-dynamische Approximationsalgorithmen zur Be- rechnung annähernd kürzester Wege in Graphen in Bezug auf die Gesamtlaufzeit, also die Summe der Laufzeiten, die jeweils benötigt werden, um das Ergebnis nach einer Änderung zu aktualisieren.