Bibliography | Buchholz, Friedhelm; Riedhofer, Bernhard: Hierarchische Graphen zur kürzesten Wegesuche in planaren Graphen. University of Stuttgart, Faculty of Computer Science, Technical Report No. 1997/13. 12 pages, german.
|
CR-Schema | F.2.2 (Nonnumerical Algorithms and Problems) G.2.2 (Graph Theory)
|
Keywords | Graph; kürzeste; Weg; Hierarchie; separator; verkehr |
Abstract | Obwohl kürzeste Wegeprobleme im Rahmen der Graphentheorie bereits ausführlich untersucht wurden, werden in den letzten Jahren im Zusammenhang mit Verkehrsinformationssystemen neue Lösungsansätze entwickelt. Dabei legt man in einer Preprocessing-Phase hierarchische Strukturen für ein gegebenes Verkehrsnetz an, so daß die kürzeste Wegesuche in dem Verkehrsnetz mit dieser Struktur effizienter erfolgen kann.
Wir führen für ungerichtete Graphen hierarchische und regionenhierarchische Graphen ein. In planaren hierarchischen und regionenhierarchischen Graphen kann die kürzeste Entfernung zwischen zwei Knoten in einer Laufzeit von O(n^{0.5}) ermittelt werden (n sei die Anzahl der Knoten in dem gegebenen Graphen). Der kürzeste Weg mit l Knoten kann in O(n^{0.5} + l) Operationen berechnet werden. Beide Typen von hierarchischen Graphen benötigen O(n^{1.5}) Platz für die Speicherung der Hilfstabellen. Während für den Aufbau von allgemeinen planaren hierarchischen Graphen O(n^2) Operationen benötigt werden, kann der Aufbau von planaren regionenhierarchischen Graphen in O(n^{1.5}) Operationen erfolgen. Beim Aufbau der hierarchischen Graphen benutzen wir insbesondere ein Separatortheorem von Lipton und Tarjan von 1979.
Die Ergebnisse wurden anhand von Experimenten mit realen Straßendaten nachgewiesen
|
Full text and other links | HTML (generated from PostScript)
|
Department(s) | University of Stuttgart, Institute of Computer Science, Formal Concepts
|
Entry date | August 21, 1997 |
---|