Simpler, faster and shorter labels for distances in graphs

DOI10.1137/1.9781611974331.CH25zbMATH Open1410.68272arXiv1504.04498OpenAlexW2952655484MaRDI QIDQ4575602FDOQ4575602

Authors: Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1504.04498

Recommendations

• Sublinear Distance Labeling
• Distance labeling in graphs
• scientific article; zbMATH DE number 1875437
• A note on exact distance labeling
• Distance labeling in graphs (extended abstract)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (24)

• Isometric universal graphs
• Better distance labeling for unweighted planar graphs
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Adjacency labeling schemes and induced-universal graphs
• Title not available (Why is that?)
• Short Labels by Traversal and Jumping
• Sublinear-space distance labeling using hubs
• 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
• Shorter Labeling Schemes for Planar Graphs
• Brief announcement: Sublinear-space distance labeling using hubs
• 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
• Title not available (Why is that?)
• Forbidden-set distance labels for graphs of bounded doubling dimension
• Succinct enumeration of distant vertex pairs
• Approximate distance labeling schemes
• Distance labeling in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Forbidden-set distance labels for graphs of bounded doubling dimension

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)