Proximity-preserving labeling schemes (Q4948512)

In this paper, methods are introduced to assign labels to vertices of a graph, such that given two labels of vertices, their distance (exactly or approximately) can be decided only by inspecting the two labels. If the exact distances can be derived, then the labeling scheme is called proximity preserving. It is shown that for trees with \(n\) vertices and edges with \(M\)-bit weights, such a proximity preserving labeling scheme exists with labels using \(O(M\log n+ \log^2n)\) bits each. For general graphs, labeling schemes that give approximate estimates for the distance are given. For a graph with \(n\) vertices and diameter \(D\), and for every \(\kappa\), there exists a labeling scheme that uses labels with \(O(\log n\cdot\log D\cdot \kappa\cdot n^{1/\kappa})\) bits each such that given two labels of vertices, the distance between the vertices can be established up to a factor of \(\sqrt{8\kappa}\). In particular, when one uses \(O(\log^2 n\log D)\) labels, then this scheme gives distance estimates which are at most a factor \(\sqrt{2\log n}\) away from the exact distance.