de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45005

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45000

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-230C-9
Abstract
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.