Item

Abstract

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.