DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Haverkort, Herman | ko |
dc.contributor.author | Lee, Mira | ko |
dc.date.accessioned | 2008-11-03T01:29:38Z | - |
dc.date.available | 2008-11-03T01:29:38Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2008-11 | - |
dc.identifier.citation | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.41, no.3, pp.188 - 205 | - |
dc.identifier.issn | 0925-7721 | - |
dc.identifier.uri | http://hdl.handle.net/10203/7724 | - |
dc.description.abstract | In a geometric network G = (S, E), the graph distance between two vertices u, nu is an element of S is the length of the shortest path in G connecting u to nu. 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 A exists. (c) 2007 Elsevier B.V. All rights reserved. | - |
dc.description.sponsorship | This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311- D00763). | en |
dc.language | English | - |
dc.language.iso | en_US | en |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | PLANAR GRAPHS | - |
dc.subject | SPANNERS | - |
dc.title | Computing a minimum-dilation spanning tree is NP-hard | - |
dc.type | Article | - |
dc.identifier.wosid | 000259133100005 | - |
dc.identifier.scopusid | 2-s2.0-49549123141 | - |
dc.type.rims | ART | - |
dc.citation.volume | 41 | - |
dc.citation.issue | 3 | - |
dc.citation.beginningpage | 188 | - |
dc.citation.endingpage | 205 | - |
dc.citation.publicationname | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
dc.identifier.doi | 10.1016/j.comgeo.2007.12.001 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Haverkort, Herman | - |
dc.contributor.nonIdAuthor | Lee, Mira | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | spanner | - |
dc.subject.keywordAuthor | dilation | - |
dc.subject.keywordAuthor | optimization | - |
dc.subject.keywordAuthor | spanning tree | - |
dc.subject.keywordAuthor | geometric network | - |
dc.subject.keywordAuthor | NP-hardness | - |
dc.subject.keywordPlus | PLANAR GRAPHS | - |
dc.subject.keywordPlus | SPANNERS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.