Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
From MaRDI portal
Publication:5252661
DOI10.1137/120884390zbMath1317.30084OpenAlexW2570705339MaRDI QIDQ5252661
Ittai Abraham, Ofer Neiman, Yair Bartal
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/120884390
Related Items
Covering metric spaces by few trees, Terminal embeddings, Covering Metric Spaces by Few Trees, On notions of distortion and an almost minimum spanning tree with constant average distortion
Cites Work
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- New length bounds for cycle bases
- Ramsey-type theorems for metric spaces with applications to online problems
- On metric Ramsey-type phenomena
- Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
- Triangulation and embedding using small sets of beacons
- Lower-stretch spanning trees
- Algorithms for Generating Fundamental Cycles in a Graph
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Using petal-decompositions to build a low stretch spanning tree
- Algorithms – ESA 2004
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Advances in metric embedding theory
- A tight bound on approximating arbitrary metrics by tree metrics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item