Title: Computing a Minimum-Dilation Spanning Tree is NP-hard. 

Speaker: Mira Lee
KAIST

Date: Wednesday Jan 24, 2007
Time 2-3PM
Venue: Room 3464, HKUST

  
Abstract:
In a geometric network G = (S, E),
the graph distance between two vertices $u, v \in S$ is the length
of the shortest path in G connecting u to v. The dilation
of G is the maximum factor by which graph distance differs from
the Euclidean distance between every pair of vertices. We show that 
given a set S of n points and a dilation \delta > 1, it is 
NP-hard to determine whether a spanning
tree of S with dilation at most \delta exists.