Hierarchical Hub Labelings for Shortest Paths

  • Ittai Abraham
  • Daniel Delling
  • Andrew Goldberg
  • Renato Werneck

MSR-TR-2012-46 |

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.