Computing a Minimum-Dilation Spanning Tree is NP-hard

Cheong, O., Haverkorty, H. and Lee, M.

    Given a set S of n points in the plane, a minimum- dilation spanning tree of S is a tree with vertex set S of smallest possible dilation. We show that given a set S of n points and a dilation XX > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most XX exists
Cite as: Cheong, O., Haverkorty, H. and Lee, M. (2007). Computing a Minimum-Dilation Spanning Tree is NP-hard. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 15-24.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS