Sunday, July 29, 2007

Minimum dilation trees- Part II

On the last day of the Dagstuhl week we (Christian Knauer and Michiel Smid) finally made some small progress. We were able to prove the following: Let G=(V,E) be a metric graph that contains a minimum dilation tree with dilation D. Given any t-spanner G' of G it hold that G' contains a tree of dilation O(t^2D^2). For some special cases it seems that we can obtain slightly better bounds. For example for a Delaunay triangulation of points in the Euclidean space where the bound probably is O(tD^2). Anyway, the proof is non-constructive so the main problem still remains. How can we find such a tree?

No comments:

Post a Comment