Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck
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.
|Published in||Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)|
|Publisher||Society for Industrial and Applied Mathematics|
Copyright © 2010 by Society for Industrial and Applied Mathematics.