Highway Dimension, Shortest Paths, and Provably Efficient Algorithms

Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck

Abstract

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of effciency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a united explanation for several seemingly different algorithms.

Details

Publication typeProceedings
Published inProc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)
PublisherSociety for Industrial and Applied Mathematics
> Publications > Highway Dimension, Shortest Paths, and Provably Efficient Algorithms