Terminal embeddings
From MaRDI portal
Publication:2405893
DOI10.1016/j.tcs.2017.06.021zbMath1378.68128arXiv1603.02321OpenAlexW4212770610MaRDI QIDQ2405893
Michael Elkin, Arnold Filtser, Ofer Neiman
Publication date: 28 September 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.02321
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)
Related Items
Lossless Prioritized Embeddings, Near isometric terminal embeddings for doubling metrics, Labelings vs. embeddings: on distributed and prioritized representations of distances, Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm, Graph spanners: a tutorial review, Dimensionality reduction for \(k\)-distance applied to persistent homology, On notions of distortion and an almost minimum spanning tree with constant average distortion, Near Isometric Terminal Embeddings for Doubling Metrics, New Results on Linear Size Distance Preservers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Competitive algorithms for distributed data management.
- An improved approximation algorithm for requirement cut
- Ramsey partitions and proximity data structures
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On sparse spanners of weighted graphs
- The dimension of almost spherical sections of convex bodies
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- Some low distortion metric Ramsey problems
- The geometry of graphs and some of its algorithmic applications
- Balancing minimum spanning trees and shortest-path trees
- On the distortion required for embedding finite metric spaces into normed spaces
- Fréchet embeddings of negative type metrics
- Measured descent: A new embedding method for finite metrics
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Prioritized Metric Structures and Embedding
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Extensions of Lipschitz mappings into a Hilbert space
- Triangulation and embedding using small sets of beacons
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Lower-Stretch Spanning Trees
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
- Approximation Algorithms for the 0-Extension Problem
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
- Small Stretch Pairwise Spanners
- Using petal-decompositions to build a low stretch spanning tree
- Euclidean distortion and the sparsest cut
- A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
- Algorithms – ESA 2004
- Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Steiner Minimal Trees
- Automata, Languages and Programming
- Euclidean Spanners in High Dimensions
- Vertex Sparsifiers: New Results from Old Techniques
- Advances in metric embedding theory
- Expander flows, geometric embeddings and graph partitioning
- A tight bound on approximating arbitrary metrics by tree metrics
