Combinatorial Theorems about Embedding Trees on the Real Line

Dartmouth Technical Report TR2005-560

	Amit Chakrabarti
	Subhash Khot

Date: October 2005

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR2005-560.pdf> (208KB)

Abstract:
 We consider the combinatorial problem of embedding a tree metric into
 the real line with low distortion. For two special families of trees ---
 the family of complete binary trees and the family of subdivided stars
 --- we provide embeddings whose distortion is provably optimal, up to a
 constant factor. We also prove that the optimal distortion of a linear
 embedding of a tree can be arbitrarily low or high even when it has
 bounded degree.