Proximity-preserving labeling schemes and their applications
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 schemes 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. Also, an application of the schemes in the context of distributed connection setup in circuit-switched networks is described. For the entire collection see [Zbl 0929.00074].
- Proximity-preserving labeling schemes
- Distance labeling in graphs (extended abstract)
- Distance labeling in graphs
- Simpler, faster and shorter labels for distances in graphs
- On distance oracles and routing in graphs
- A note on exact distance labeling
- Labeling Schemes for Small Distances in Trees
- scientific article; zbMATH DE number 2079400
- Distance labeling scheme and split decomposition
- Algorithms and Computation
- A note on models for graph representations
- Distance labeling schemes for well-separated graph classes
- Distance estimation and object location via rings of neighbors
- General compact labeling schemes for dynamic trees
- Randomized proof-labeling schemes
- Light spanners for high dimensional norms via stochastic decompositions
- Tree-decompositions with bags of small diameter
- Average case analysis for tree labelling schemes
- Distributed distance computation and routing with small messages
- Labeling schemes for weighted dynamic trees
- Max-stretch reduction for tree spanners
- Informative labeling schemes for graphs
- Informative labeling schemes for graphs (extended abstract)
- Proximity-preserving labeling schemes
- Light spanners for high dimensional norms via stochastic decompositions
- List graphs and distance-consistent node labelings
- Lossless prioritized embeddings
- Compact and localized distributed data structures
- Distance labeling for families of cycles
- A note on distance labeling of graphs
- Massively parallel computation in a heterogeneous regime
- Spanner approximations in practice
- Constructing labeling schemes through universal matrices
This page was built for publication: Proximity-preserving labeling schemes and their applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4944965)
