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 into the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach practical for a wider class of graphs. We also fifind smaller labels for road networks, improving the query speed.

Details

Publication typeInproceedings
Published inProceedings of the 20th Annual European Symposium on Algorithms (ESA'12)
SeriesLecture Notes in Computer Science
PublisherSpringer
> Publications > Hierarchical Hub Labelings for Shortest Paths