A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node @math stores its distance to all nodes from an appropriately chosen set of hubs @math . For a queried pair of nodes @math , the length of a shortest @math -path passing through a hub node from @math is then used as an upper bound on the distance between @math and @math . We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most @math nodes and average degree @math , the tradeoff between label bit size @math and query decoding time @math for our approach is given by @math , for any @math . Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant @math , we can achieve any @math while maintaining @math ), and it also provides an improvement in terms of label size with respect to previous slower approaches. By using similar techniques, we then present a @math -additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve almost the same label size-time tradeoff @math , for any @math . To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any @math is sufficient).
The distance labeling problem in undirected graphs was first investigated by Graham and Pollak @cite_13 , who provided the first labeling scheme with labels of size @math . The decoding time for labels of size @math was subsequently improved to @math by Gavoille al @cite_4 and to @math by Weimann and Peleg @cite_7 . Finally, Alstrup al @cite_1 present a scheme for general graphs with decoding in @math time using labels of size @math bits. For the sake of sanity of the notation, we define @math . This matches up to low order terms the space of the currently best known distance oracle with @math time and @math total space in a memory model, due to Nitto and Venturini @cite_24 .
@cite_4 @cite_7 @cite_1 @cite_24 @cite_13
2952655484 756611012 2952839955 2074619214
We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label lenght and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different trade-offs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. More specifically, we present a distance labeling scheme with label size (log 3) 2 + o(n) (logarithms are in base 2) and O(1) decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n log n) decoding time, and (SODA'01), which uses labels of size 11n + o(n) and O(loglog n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for label sizes. For r-additive approximation schemes, where distances can be off by an additive constant r, we give both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency scheme: n 2. We also give results for bipartite graphs and for exact and 1-additive distance oracles. A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present the first distance labeling scheme of size opnq for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et. al. [J. Algo. 2004], hereby separating the complexity from general graphs which require pnq size Moon [Proc. of Glasgow Math. Association 1965]. As an intermediate result we give a Op n D log 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 show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between any two vertices can be inferred from their labels alone in O(log^@?n) time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but O(loglogn) time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length @W(n).