KIT | KIT-Bibliothek | Impressum | Datenschutz

Heuristic Contraction Hierarchies with Approximation Guarantee

Geisberger, Robert; Schieferdecker, Dennis


We present a new heuristic point-to-point shortest path algorithm based on contraction hierarchies (CH). Given an epsilon > 0, we can prove that the length of the path computed by our algorithm is at most (1 + epsilon) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid adding shortcuts even when a replacement path is (1 + epsilon) times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.

Volltext §
DOI: 10.5445/IR/1000020377
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2010
Sprache Englisch
Identifikator ISBN: 978-1-57735-481-9
KITopen-ID: 1000020377
Erschienen in Proceedings of the Third International Symposium on Combinatorial Search (SoCS 2010), Atlanta, Georgia USA, 8-10 July, 2010. Ed.: N. Sturtevant
Verlag AAAI Publications
Seiten 14 S.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page