Computing a minimum-dilation spanning tree is NP-hard

O. Cheong, H.J. Haverkort, M. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the 13th Computing: the Australasian Theory Symposium (CATS 2007) 30 January - 2 February 2007, Ballarat, Victoria, Australia
EditorsJ. Gudmundsson, B. Jay
Place of PublicationSydney
PublisherAustralian Computer Society
Pages15-24
ISBN (Print)1-920-68246-5
Publication statusPublished - 2007
Eventconference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02 -
Duration: 30 Jan 20072 Feb 2007

Publication series

NameConferences in Research and Practice in Information Technology
Volume65
ISSN (Print)1445-1336

Conference

Conferenceconference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02
Period30/01/072/02/07
OtherCATS 2007, Ballarat, Victoria, Australia

Fingerprint

Dive into the research topics of 'Computing a minimum-dilation spanning tree is NP-hard'. Together they form a unique fingerprint.

Cite this