The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) @math V to each node u @math V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) @math S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.
Highway dimension @math guarantees the existence of distance labels of size @math where @math is the weighted diameter of the graph @cite_14 . However, when restricting to polynomial time algorithms, such labels can only be approximated within a @math factor using shortest path cover algorithms @cite_14 or a @math factor with a more involved procedure based on VC-dimension @cite_12 . In any case, this requires an all-pair shortest path computation. For large networks, labels can be practically computed when classical heuristics such as contraction hierarchies (CH) can be performed @cite_14 @cite_19 @cite_22 . Low highway dimension guarantees that there exists an elimination ordering for CH such that the graph produced has bounded size @cite_14 . However, it does not ensure running time faster than all pair shortest path computation.
@cite_19 @cite_14 @cite_22 @cite_12
2112513979 2146583842 85521454
[SODA 2010] have recently presented a theoretical analysis of several practical point-to-point shortest path algorithms based on modeling road networks as graphs with low highway dimension. They also analyze a labeling algorithm. While no practical implementation of this algorithm existed, it has the best time bounds. This paper describes an implementation of the labeling algorithm that is faster than any existing method on continental road networks. 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 find smaller labels for road networks, improving the query speed. We explore the relationship between VC-dimension and graph algorithm design. In particular, we show that set systems induced by sets of vertices on shortest paths have VC-dimension at most two. This allows us to use a result from learning theory to improve time bounds on query algorithms for the point-to-point shortest path problem in networks of low highway dimension, such as road networks. We also refine the definitions of highway dimension and related concepts, making them more general and potentially more relevant to practice. In particular, we define highway dimension in terms of set systems induced by shortest paths, and give cardinality-based and average case definitions.