Type of Publication: | Diploma thesis |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-10385 |
Author: | Holzer, Martin |
Year of publication: | 2003 |
Summary: |
Shortest-path problems occur in many fields of application, where the graphs are often
very large and queries have to be answered in 'real-time'. This cannot be overcome by the classical algorithm of Dijkstra but requires more sophisticated speed-up techniques. One approach consists of hierarchical decomposition of a given graph and pre-computation of information in order to reduce search space during the on-line stage. One such technique applied to a specific scenario was recently investigated in a systematic experimental study. In the following work, we follow up and give a detailed analysis of this speed-up technique along with experiments using several graph classes. |
Subject (DDC): | 004 Computer Science |
Controlled Keywords (GND): | Algorithmus, Beschleunigung, Graph, Pfad, Weg |
Keywords: | hierarchisch, kürzest, Verschnellerung, Beschleunigungstechnik, algorithm, speed-up, graph, path, shortest |
Link to License: | In Copyright |
HOLZER, Martin, 2003. Hierarchical speed-up techniques for shortest-path algorithms [Master thesis]
@mastersthesis{Holzer2003Hiera-6098, title={Hierarchical speed-up techniques for shortest-path algorithms}, year={2003}, author={Holzer, Martin} }
da_finished.pdf | 283 |