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.

PDF file

Publisher  Microsoft Research

Details