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).
We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional information). Our main interest is in the minimal length of labels needed in different cases. We obtain upper and lower bounds for several interesting families of graphs. In particular, our main results are the following. For general graphs, we show that the length needed is Θ(n). For trees, we show that the length needed is Θ(log2 n). For planar graphs, we show an upper bound of O(√nlogn) and a lower bound of Ω(n1 3). For bounded degree graphs, we show a lower bound of Ω(√n). The upper bounds for planar graphs and for trees follow by a more general upper bound for graphs with a r(n)-separator. The two lower bounds, however, are obtained by two different arguments that may be interesting in their own right. We also show some lower bounds on the length of the labels, even if it is only required that distances be approximated to a multiplicative factor s. For example, we show that for general graphs the required length is Ω(n) for every s < 3. We also consider the problem of the time complexity of the distance function once the labels are computed. We show that there are graphs with optimal labels of length 3 log n, such that if we use any labels with fewer than n bits per label, computing the distance function requires exponential time. A similar result is obtained for planar and bounded degree graphs. 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). 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. Let G be an unweighted and undirected graph of n nodes, and let D be the nxn matrix storing the All-Pairs-Shortest-Path Distances in G. Since D contains integers in [n]@?+ , its plain storage takes n^2log(n+1) bits. However, a simple counting argument shows that n^2 2 bits are necessary to store D. In this paper we investigate the question of finding a succinct representation of D that requires O(n^2) bits of storage and still supports constant-time access to each of its entries. This is asymptotically optimal in the worst case, and far from the information-theoretic lower bound by a multiplicative factor log"23 1.585. As a result O(1) bits per pairs of nodes in G are enough to retain constant-time access to their shortest-path distance. We achieve this result by reducing the storage of D to the succinct storage of labeled trees and ternary sequences, for which we properly adapt and orchestrate the use of known compressed data structures. This approach can be easily and optimally extended to graphs whose edge weights are positive integers bounded by a constant value. We shall refer to d((s 1 ..... Sn) , (s ..... s )) as the distance be! I tween the two n-tuples (s I ..... Sn) and (s 1 ..... s n) although, strictly speaking• this is an abuse of terminology since d does not satisfy the triangle inequality. For a connected graph G, the distance between two vertices v and v' in G, denoted by dG(V,V'), is defined to be the minimum number of edges in any path between v and v'. The following problem arose recently in connection with a data transmission scheme of J. R. Pierce [4].