Computing a Minimum-Dilation Spanning Tree is NP-hard

Simple item page
dc.creatorCheong, Otfried
dc.creatorHaverkort, Herman
dc.creatorLee, Mira
dc.date2007-03-06
dc.date.accessioned2026-07-07T07:50:22Z
dc.date.available2026-07-07T07:50:22Z
dc.descriptionIn 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 the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
dc.identifierhttps://arxiv.org/abs/cs/0703023
dc.identifierhttp://arxiv.org/abs/cs/0703023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/125143
dc.subjectComputational Geometry
dc.titleComputing a Minimum-Dilation Spanning Tree is NP-hard
dc.typetext

Files

Collections

arXiv