BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2005-560
ENTRY:: October 17, 2005
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Combinatorial Theorems about Embedding Trees on the Real Line
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Chakrabarti, Amit
AUTHOR:: Khot, Subhash
DATE:: October 2005
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2005-560.pdf
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.
END:: ncstrl.dartmouthcs//TR2005-560