Sublinear-space distance labeling using hubs

DOI10.1007/978-3-662-53426-7_17MaRDI QIDQ1660937zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Adrian Kosowski, Przemysław Uznański

Publication date 16 August 2018

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Abstract: 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 $u$ stores its distance to all nodes from an appropriately chosen set of hubs $S(u)subseteqV$. For a queried pair of nodes $(u,v)$, the length of a shortest $u-v$-path passing through a hub node from $S(u)capS(v)$ is then used as an upper bound on the distance between $u$ and $v$. 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 $n$ nodes and average degree $Delta$, the tradeoff between label bit size $L$ and query decoding time $T$ for our approach is given by $L=O(nloglo{g}_{D}eltaT/lo{g}_{D}eltaT)$, for any $Tleqn$. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant $Delta$, we can achieve any $T=omega(1)$ while maintaining $L=o(n)$), 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 $2$-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 $L=O(nlo{g}^{2}logT/logT)$, for any $Tleqn$. 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 $T=omega(1)$ is sufficient).

Recommendations

• Brief announcement: Sublinear-space distance labeling using hubs
• Sublinear Distance Labeling
• Simpler, faster and shorter labels for distances in graphs
• Hardness of exact distance queries in sparse graphs through hub labeling
• scientific article; zbMATH DE number 1875437

Cited in

(14)

• Better distance labeling for unweighted planar graphs
• Isometric universal graphs
• Beyond highway dimension: small distance labels using tree skeletons
• Fault-tolerant distance labeling for planar graphs
• Hardness of exact distance queries in sparse graphs through hub labeling
• Better distance labeling for unweighted planar graphs
• Near-optimal distance emulator for planar graphs
• scientific article; zbMATH DE number 7765385 (Why is no real title available?)
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Brief announcement: Sublinear-space distance labeling using hubs
• Shorter Labeling Schemes for Planar Graphs
• Eccentricity queries and beyond using hub labels
• Distance and routing labeling schemes for cube-free median graphs
• Sublinear Distance Labeling

This page was built for publication: Sublinear-space distance labeling using hubs

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