Bibliography | Hosseyni Damabi, Seyed Pedram: Contraction Hierarchies für kontinuierliche Graphsimplifizierung. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 25 (2016). 49 pages, german.
|
CR-Schema | G.2.2 (Discrete Mathematics Graph Theory) I.3.5 (Computational Geometry and Object Modeling) J.2 (Physical Sciences and Engineering)
|
Abstract | Mithilfe von Contraction Hierarchies lassen sich kürzeste Pfade eines Graphen effizient finden. Hierbei findet vor der eigentlichen Suche des kürzesten Pfades eine Vorverarbeitung statt, deren zentrale Operation die Kontraktion von Knoten ist. Hierbei wird der entsprechende Knoten zunächst aus dem Graphen entfernt; falls dadurch die kürzeste-Wege-Distanz der benachbarten Knoten vergrößert wird, werden dem Graphen neue Kanten, sogenannte Shortcuts, hinzugefügt. Durch die iterative Entfernung der Knoten kann jedoch auch eine Simplifizierung des Originalgraphen durchgeführt werden. Hierzu werden in dieser Arbeit verschiedene Kontraktionsreihenfolgen untersucht. Die betrachteten Kriterien zur Sortierung der Knoten sind die Edge Difference, die räumliche Dichte der Knoten, die durchschnittliche Kantendistanz der zum Knoten inzidenten Kanten sowie (bei Knoten vom Grad zwei) der Winkel der zum Knoten inzidenten Kanten. Hierzu wird ein Verfahren erläutert, mit dem die unterschiedlichen Kriterien miteinander kombiniert werden können. Des Weiteren wird ein Verfahren vorgestellt, mit dem aus der Ausgabe der Vorverarbeitung ein simplifizierter Graph erzeugt werden kann. Dabei werden Knoten abhängig vom Zeitpunkt ihrer Kontraktion aus dem Graphen entfernt. Von den verbleibenden Kanten werden zu lange Shortcuts rekursiv entpackt, d.h. durch die ursprünglichen Kanten ersetzt.
|
Full text and other links | PDF (5091284 Bytes)
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
Superviser(s) | Funke, Prof. Stefan |
Entry date | September 26, 2018 |
---|