Kürzeste-Wege-Berechnung bei sehr großen Datenmengen

In diesem Report untersuchen wir die Ein/Ausgabe-Komplexität (I/O Komplexität) des Kürzesten-Wege-Problems mit einem Startknoten (single source shortest path) auf Graphen mit nicht-negativen Kantengewichten. Wir präsentieren einen Algorithmus, der für eine große Klasse zufälliger Graphen eine I/O Komplexität von ${\cal O}(\frac{n}{D}+\frac{m}{DB}\log_{S/B}\frac{m}{B})$ erreicht. Dabei bezeichnen $n,m$ die Anzahl der Knoten bzw. Kanten im Graphen, $S$ ist die Größe des verfügbaren Internspeichers, $B$ bezeichnet die Größe eines Blocktransfers und $D$ ist die Anzahl der unabhängigen parallelen Harddisks; $D$ ist beschränkt auf ${\cal O}(\sqrt{n/d})$. Weiterhin präsentieren wir ein effizientes Phasen-Verfahren für Probleminstanzen, die so groß sind, daß selbst ein boolsches Feld für die Knotenmenge nicht mehr im Hauptspeicher gehalten werden kann