For fixed @math , we consider the task of adding to a graph @math a set of weighted shortcut edges on the same vertex set, such that the length of a shortest @math -hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in @math . A set of shortcut edges with this property is called an exact @math -hopset and may be applied in processing distance queries on graph @math . In particular, a @math -hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on @math -hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that @math -hopsets require exponentially fewer shortcuts per node than any previously described distance oracle while incurring only a quadratic increase in the query decoding time, and actually offer a speedup when compared to simple oracles based on a direct application of @math -hopsets. Finally, we consider the problem of computing minimum-size @math -hopset (for any @math ) for a given graph @math , showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When @math , for a given bound on the space used by the distance oracle, we provide a construction of hopsets achieving polylog approximation both for space and query time compared to the optimal @math -hopset oracle given the space bound.
In graphs of bounded highway dimension, hub labels were among the first identified distance oracles to provide label size and query time polynomial in the highway dimension and polylogarithmic in other graph parameters @cite_18 . This result was then extended to the more general class of graphs with bounded skeleton dimension @cite_4 .
@cite_18 @cite_4
2952839955 63325702 2964124596 2550610852
Consider an undirected weighted graph G=(V,E) with |V|=n and |E|=m, where each vertex v is assigned a label from a set L of labels. We show how to construct a compact distance oracle that can answer queries of the form: "what is the distance from v to the closest lambda-labeled node" for a given node v in V and label lambda in L. This problem was introduced by Hermelin, Levy, Weimann and Yuster [ICALP 2011] where they present several results for this problem. In the first result, they show how to construct a vertex-label distance oracle of expected size O(kn^ 1+1 k ) with stretch (4k - 5) and query time O(k). In a second result, they show how to reduce the size of the data structure to O(kn ^ 1 k ) at the expense of a huge stretch, the stretch of this construction grows exponentially in k, (2^k-1). In the third result they present a dynamic vertex-label distance oracle that is capable of handling label changes in a sub-linear time. The stretch of this construction is also exponential in k, (2 3^ k-1 +1). We manage to significantly improve the stretch of their constructions, reducing the dependence on k from exponential to polynomial (4k-5), without requiring any tradeoff regarding any of the other variables. In addition, we introduce the notion of vertex-label spanners: subgraphs that preserve distances between every node v and label lambda. We present an efficient construction for vertex-label spanners with stretch-size tradeoff close to optimal. We consider vertex-labeled graphs, where each vertex v is attached with a label from a set of labels. The vertex-to-label distance query desires the length of the shortest path from the given vertex to the set of vertices with the given label. We show how to construct an oracle for a vertex-labeled planar graph, such that (O( 1 n n) ) storing space is needed, and any vertex-to-label query can be answered in (O( 1 n ) ) time with stretch 1 + e. Here, Δ is the hop-diameter of the given graph. For the case that Δ = O(logn), we construct a distance oracle that achieves (O( 1 n) ) query time, without changing space usage. The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) ⊆ V to each node u ∈ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) ∩ 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. There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of Ω(log n) for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously. Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an O(log D) approximation algorithm for graphs of shortest-path diameter D with unique shortest paths. In particular, we get an O(log log n) approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an O(log n) approximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial-time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2.