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

Ittai Abraham, Yair Bartal, Ofer Neiman

This paper addresses the basic question of how well can a tree approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a g…