Lower bounds on the distortion of embedding finite metric spaces in graphs
From MaRDI portal
Publication:1380790
DOI10.1007/PL00009336zbMath0890.05021MaRDI QIDQ1380790
Publication date: 22 June 1998
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Related Items (27)
On approximating tree spanners that are breadth first search trees ⋮ Metric Characterizations of Some Classes of Banach Spaces ⋮ Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs ⋮ Metric embedding, hyperbolic space, and social networks ⋮ Truly Optimal Euclidean Spanners ⋮ Covering metric spaces by few trees ⋮ Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Prioritized Metric Structures and Embedding ⋮ Stochastic approximation of lamplighter metrics ⋮ Approximating spaces of Nagata dimension zero by weighted trees ⋮ Distortion of embeddings of binary trees into diamond graphs ⋮ Tree spanners of bounded degree graphs ⋮ Maximum gradient embeddings and monotone clustering ⋮ Pathwidth, trees, and random embeddings ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ Advances in metric embedding theory ⋮ Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ Nonlinear spectral calculus and super-expanders ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Covering Metric Spaces by Few Trees ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ On approximating planar metrics by tree metrics.
This page was built for publication: Lower bounds on the distortion of embedding finite metric spaces in graphs
