Sunday, July 29, 2007
Minimum dilation trees- Part II
Posted by
Joachim
at
4:34 AM
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?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment