Hierarchical speed-up techniques for shortest-path algorithms

Holzer, Martin

Hierarchical speed-up techniques for shortest-path algorithms

Publikationstyp:	Masterarbeit/Diplomarbeit
URI (zitierfähiger Link):	http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-10385
Autor/innen:	Holzer, Martin
Erscheinungsjahr:	2003
Zusammenfassung:	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.
Fachgebiet (DDC):	004 Informatik
Normierte Schlagwörter (GND):	Algorithmus, Beschleunigung, Graph, Pfad, Weg
Schlagwörter:	hierarchisch, kürzest, Verschnellerung, Beschleunigungstechnik, algorithm, speed-up, graph, path, shortest
Link zur Lizenz:	Nutzungsbedingungen

Zitieren

Dateien zu dieser Ressource

Name: da_finished.pdf

Größe: 934.2Kb

Format: PDF

Öffnen

Prüfsumme: MD5:404e12b0cee91e220deb3b8a502c03be

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} }

terms-of-use application/pdf Hierarchical speed-up techniques for shortest-path algorithms Holzer, Martin eng Holzer, Martin 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. 2011-03-24T16:09:32Z 2003 2011-03-24T16:09:32Z