|
| | | |
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. |
(from crpit.com)
(local if available)
|
|