KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-149522

Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm

Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea

Abstract:
In "Combining Speed-up Techniques for Shortest-Path Computations", basic speed-up techniques for Dijkstra's algorithm have been combined. The key observation in this work was that it is most promising to combine hierarchical and goal-directed speed-up techniques. However, since its publication, impressive progress has been made in the field of speed-up techniques for Dijkstra’s algorithm and huge data sets have been made available.
Hence, we revisit the systematic combination of speed-up techniques in this work, which leads to the fastest known algorithms for various scenarios. Even for road networks, which have been worked on heavily during the last years, we are able to present an improvement in performance. Moreover, we gain interesting insights into the behavior of speed-up techniques when combining them.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2008
Sprache Englisch
Identifikator ISBN: 978-3-540-68548-7
ISSN: 0302-9743
KITopen ID: 1000014952
Erschienen in Experimental Algorithms. 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30 - June 1, 2008. proceedings Ed.: C.C. McGeoch
Verlag Springer Berlin / Heidelberg
Seiten 303-318
Serie Lecture Notes in Computer Science ; 5038
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page