Simpler, faster and shorter labels for distances in graphs
From MaRDI portal
Publication:4575602
Abstract: 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 Gavoille et al. (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.
Recommendations
Cited in
(24)- Forbidden-set distance labels for graphs of bounded doubling dimension
- Better distance labeling for unweighted planar graphs
- Isometric universal graphs
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- Adjacency labeling schemes and induced-universal graphs
- scientific article; zbMATH DE number 7561659 (Why is no real title available?)
- Sublinear-space distance labeling using hubs
- Short Labels by Traversal and Jumping
- Proximity-preserving labeling schemes
- Better distance labeling for unweighted planar graphs
- Near-optimal distance emulator for planar graphs
- Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes
- Brief announcement: Sublinear-space distance labeling using hubs
- Shorter Labeling Schemes for Planar Graphs
- Optimal distance labeling for interval and circular-arc graphs
- On approximate distance labels and routing schemes with affine stretch
- Distance and routing labeling schemes for cube-free median graphs
- scientific article; zbMATH DE number 1875437 (Why is no real title available?)
- Forbidden-set distance labels for graphs of bounded doubling dimension
- Approximate distance labeling schemes
- Succinct enumeration of distant vertex pairs
- Distance labeling in graphs
- scientific article; zbMATH DE number 1830738 (Why is no real title available?)
- scientific article; zbMATH DE number 1420896 (Why is no real title available?)
This page was built for publication: Simpler, faster and shorter labels for distances in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575602)
