Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Hierarchical Hub Labelings for Shortest Paths

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

Abstract

We study hierarchical hub labelings for computing shortest paths. Our new theoretical insights on the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach practical for a wider class of graphs and enabling real-time traffic updates on road networks. We also find smaller labels, improving the query speed.

Details

Publication typeTechReport
NumberMSR-TR-2012-46
PublisherMicrosoft Research
> Publications > Hierarchical Hub Labelings for Shortest Paths