@inproceedings{bdaa0637b37d435dbd8deaa912ed38ed,

title = "Computing a minimum-dilation spanning tree is NP-hard",

abstract = "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 d > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most d exists.",

author = "O. Cheong and H.J. Haverkort and M. Lee",

year = "2007",

language = "English",

isbn = "1-920-68246-5",

series = "Conferences in Research and Practice in Information Technology",

publisher = "Australian Computer Society",

pages = "15--24",

editor = "J. Gudmundsson and B. Jay",

booktitle = "Proceedings of the 13th Computing: the Australasian Theory Symposium (CATS 2007) 30 January - 2 February 2007, Ballarat, Victoria, Australia",

address = "Australia",

note = "conference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02 ; Conference date: 30-01-2007 Through 02-02-2007",

}