Hierarchische Graphen zur Wegesuche

Abstract

In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design, Verteiltes Rechnen und geometrische und parallele Algorithmen. In einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer Graph (HG) konstruiert, der in der Online-Phase zur Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T) der Preprocessing-Phase, die Groesse (S) des HG'en und die Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge kann bis auf einen logarithmischen Faktor und bezueglich des Umgebungsabstands bis auf einen konstanten Faktor in polynomieller Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990 und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von fast linearer Groesse genuegen, um Q in O(n {1.5} log 3 n) zu gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren optimal. Ausserdem wird ein neuer Parameter 'Separatorweite' fuer Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel wird gezeigt, dass eine logarithmische Abweichung auftreten kann.

In this work a two-phasemodel for efficient shortest-path-queries in weighted graphs is examined. Applications are traffic-information-systems, VLSI-design, distributed computing and geometric and parallel algorithms. In a preprocessing-phase a hierarchical graph (HG) is determined, which can be used efficiently for answering shortest-path-queries in an online-phase. I examine especially the running time of the preprocessing-phase (T) and of the online-phase (Q) and the size of the HG (S). I present two different approaches: appropriate vertices and a recursive separation method. I generalize appropriate vertices to levelgraphs and show the NP-completeness of the determination of a minimal appropriate vertex set. For a minimal appropriate vertex set a log-approximation and for the minimal surrounding distance a 2-approximation can be done in polynomial time. I give the algorithms. In the case of planar graphs I extend the separation method to construct HG's of nearly linear size and show Q in O(n {1.5} log 3 n). This result is optimal modulo logarithmic factors. Furthermore I introduce a new parameter for graphs called the separatorwidth and show its independence of treewidth. Both parameters differ at most up to a logarithmic factor. By giving an example, I show that this can happen.