Highway Dimension and Provably Efficient Shortest Path Algorithms
We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.
Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck