Separating Hierarchical and General Hub Labelings

Andrew V. Goldberg, Ilya Razenshteyn, Ruslan Savchenko

In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An $s,t$ query computes the corresponding distance from the labels of $s$ and…