Labelings vs. embeddings: on distributed and prioritized representations of distances
From MaRDI portal
Publication:6124827
DOI10.1007/s00454-023-00565-2MaRDI QIDQ6124827
Robert Krauthgamer, Lee-Ad J. Gottlieb, Arnold Filtser
Publication date: 2 April 2024
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-023-00565-2
05C12: Distance in graphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
46B85: Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
30L05: Geometric embeddings of metric spaces
68R12: Metric embeddings as related to computational problems and algorithms
Cites Work
- Unnamed Item
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Graph minors. XVI: Excluding a non-planar graph
- Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings
- The geometry of graphs and some of its algorithmic applications
- On the distortion required for embedding finite metric spaces into normed spaces
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- Terminal embeddings
- Measured descent: A new embedding method for finite metrics
- Prioritized Metric Structures and Embedding
- Extensions of Lipschitz mappings into a Hilbert space
- Approximate distance oracles
- Distance labeling in graphs
- Near Isometric Terminal Embeddings for Doubling Metrics
- Lossless Prioritized Embeddings
- Labelings vs. Embeddings: On Distributed Representations of Distances
- Object location using path separators
- Optimal terminal dimensionality reduction in Euclidean space
- Metric embedding via shortest path decompositions
- Compact oracles for reachability and approximate distances in planar digraphs
- Advances in metric embedding theory
- Geometry of cuts and metrics
- A tight bound on approximating arbitrary metrics by tree metrics
