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

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