Optimal distance labeling schemes for trees

DOI10.1145/3087801.3087804MaRDI QIDQ5368961zbMATH OpenOpenAlexFDO

Authors Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson, Oren Weimann

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

labeling schemeuniversal tree

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. For the particular case of trees, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS'15], nearest common ancestor labeling [SODA'14], and ancestry labeling [SICOMP'06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size $1/4lo{g}^{2}n+o(lo{g}^{2}n)$, matching (up to low order terms) the recent $1/4lo{g}^{2}n-O(logn)$ lower bound [ICALP'16]. Prior to our work, all distance labeling schemes for trees could be reinterpreted as universal trees. A tree $T$ is said to be universal if any tree on $n$ nodes can be found as a subtree of $T$. A universal tree with $|T|$ nodes implies a distance labeling scheme with label size $log|T|$. In 1981, Chung et al. proved that any distance labeling scheme based on universal trees requires labels of size $1/2lo{g}^{2}n-logncdotloglogn+O(logn)$. Our scheme is the first to break this lower bound, showing a separation between distance labeling and universal trees. The $Theta(lo{g}^{2}n)$ barrier has led researchers to consider distances bounded by $k$. The size of such labels was improved from $logn+O(ksqrtlogn)$ [WADS'01] to $logn+O(k^2(log(klogn))$ [SODA'03] and then to $logn+O(klog(klog(n/k)))$ [PODC'07]. We show how to construct labels whose size is $minlogn+O(klog((logn)/k)),O(logncdotlog(k/logn))$. We complement this with almost tight lower bounds of $logn+Omega(klog(logn/(klogk)))$ and $Omega(logncdotlog(k/logn))$. Finally, we consider $(1+varepsilon)$-approximate distances. We show that the labeling scheme of [ICALP'16] can be easily modified to obtain an $O(log(1/varepsilon)cdotlogn)$ upper bound and we prove a $Omega(log(1/varepsilon)cdotlogn)$ lower bound.

Recommendations

• scientific article; zbMATH DE number 2079400
• Labeling Schemes for Small Distances in Trees
• Distance labeling schemes for trees
• Algorithms and Computation
• Average case analysis for tree labelling schemes

Cited in

(28)

• An optimal algorithm to reconstruct trees from additive distance data
• Distance labeling schemes for \(K_4\)-free bridged graphs
• Distance and routing labeling schemes for cube-free median graphs
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• Distance labeling schemes for trees
• Labeling schemes for nearest common ancestors through minor-universal trees
• Optimal induced universal graphs and adjacency labeling for trees
• Distance labeling in graphs
• Isometric universal graphs
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Distance labeling schemes for cube-free median graphs
• Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs
• Labeling schemes for bounded degree graphs
• Near-optimal labeling schemes for nearest common ancestors
• On local representation of distances in trees
• Constructing Labeling Schemes Through Universal Matrices
• Labeling Schemes for Small Distances in Trees
• Shorter Labeling Schemes for Planar Graphs
• Algorithms and Computation
• scientific article; zbMATH DE number 7765385 (Why is no real title available?)
• Better distance labeling for unweighted planar graphs
• Distance labeling for families of cycles
• Closing the gap: minimum space optimal time distance labeling scheme for interval graphs
• Optimal Euclidean tree covers
• Optimal distance labeling for permutation graphs
• Better distance labeling for unweighted planar graphs
• Optimal radio labellings of complete m-ary trees
• Constructing labeling schemes through universal matrices

This page was built for publication: Optimal distance labeling schemes for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368961)