Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion

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

zbMATH Keywords

embeddingsdistortionfinite metric spacesspanning treesultrametric spaces

Mathematics Subject Classification ID

Geometric embeddings of metric spaces (30L05)

Related Items (4)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion