Hub labels: Theory and practice

Abstract. The Hub Labeling algorithm (HL) is an exact shortest path algorithm with excellent query performance on some classes of problems. It precomputes some auxiliary information (stored as a label) for each vertex, and its query performance depends only on the label size. While there are polynomial-time approximation algorithms to find labels of ap-proximately optimal size, practical solutions use hierarchical hub labels (HHL), which are faster to compute but offer no guarantee on the la-bel size. We improve the theoretical and practical performance of the HL approximation algorithms, enabling us to compute such labels for moderately large problems. Our comparison shows that HHL algorithms scale much better and find labels that usually are not much bigger than the theoretically justified HL labels.