On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

Steiner minimal trees

E. N. Gilbert and H. O. Pollak · 1968

Earlier work this paper cites.

Efficient broadcast and light-weight spanners

B. Awerbuch, A. Baratz, and D. Peleg · 1992

Earlier work this paper cites.

New sparseness results on graph spanners

Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares · 1992

Earlier work this paper cites.

Balancing minimum spanning and shortest path trees

Samir Khuller, Balaji Raghavachari, and Neal E. Young · 1993

Earlier work this paper cites.

A graph-theoretic game and its application to the

Noga Alon, Richard M. Karp, David Peleg, and Douglas West · 1995

Earlier work this paper cites.

Probabilistic approximation of metric spaces and its algorithmic applications

Yair Bartal · 1996

Earlier work this paper cites.

On approximating arbitrary metrices by tree metrics

Yair Bartal · 1998

Earlier work this paper cites.

A tight bound on approximating arbitrary metrics by tree metrics

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar · 2003

Earlier work this paper cites.

Graph decomposition lemmas and their role in metric embedding methods

Yair Bartal · 2004

Earlier work this paper cites.

Metric embeddings with relaxed guarantees

Ittai Abraham, Yair Bartal, Hubert T.-H. Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, and Aleksandrs Slivkins · 2005

Cited alongside, same era.

Spanners with slack

T.-H. Hubert Chan, Michael Dinitz, and Anupam Gupta · 2006

Cited alongside, same era.

Nearly tight low stretch spanning trees

Ittai Abraham, Yair Bartal, and Ofer Neiman · 2008

Cited alongside, same era.

Lower-stretch spanning trees

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng · 2008

Cited alongside, same era.

Triangulation and embedding using small sets of beacons

Jon Kleinberg, Aleksandrs Slivkins, and Tom Wexler · 2009

Cited alongside, same era.

Advances in metric embedding theory

Ittai Abraham, Yair Bartal, and Ofer Neiman · 2011

Cited alongside, same era.

Light spanners

Michael Elkin, Ofer Neiman, and Shay Solomon · 2014

Later among the works it cites.

Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion

Ittai Abraham, Yair Bartal, and Ofer Neiman · 2015

Later among the works it cites.

Prioritized metric structures and embedding

Michael Elkin, Arnold Filtser, and Ofer Neiman · 2015

Later among the works it cites.

Terminal embeddings

Michael Elkin, Arnold Filtser, and Ofer Neiman · 2015

Later among the works it cites.

On notions of distortion and an almost minimum spanning tree with constant average distortion

Yair Bartal, Arnold Filtser, and Ofer Neiman · 2016

Closest in time.

Near-optimal light spanners

Shiri Chechik and Christian Wulff-Nilsen · 2016

Closest in time.