Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

MPG-Autoren
/persons/resource/persons45005

Maue,  Jens
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45000

Matijevic,  Domagoj
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Maue, J., Sanders, P., & Matijevic, D. (2006). Goal Directed Shortest Path Queries Using Precomputed Cluster Distances. In Experimental Algorithms, 5th International Workshop, WEA 2006 (pp. 316-327). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-230C-9
Zusammenfassung
We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong ``sense of direction''. We evaluate our approach experimentally using large, real-world road networks.