DSpace at KOASAS
College of Engineering(공과대학)School of Computing(전산학부)CS-Journal Papers(저널논문)

Computing a minimum-dilation spanning tree is NP-hard

Cited 12 time in webofscience Cited 16 time in scopus
  • Hit : 1679
  • Download : 861
Export
DC FieldValueLanguage
dc.contributor.authorCheong, Otfriedko
dc.contributor.authorHaverkort, Hermanko
dc.contributor.authorLee, Mirako
dc.date.accessioned2008-11-03T01:29:38Z-
dc.date.available2008-11-03T01:29:38Z-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.issued2008-11-
dc.identifier.citationCOMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.41, no.3, pp.188 - 205-
dc.identifier.issn0925-7721-
dc.identifier.urihttp://hdl.handle.net/10203/7724-
dc.description.abstractIn 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.sponsorshipThis research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311- D00763).en
dc.languageEnglish-
dc.language.isoen_USen
dc.publisherELSEVIER SCIENCE BV-
dc.subjectPLANAR GRAPHS-
dc.subjectSPANNERS-
dc.titleComputing a minimum-dilation spanning tree is NP-hard-
dc.typeArticle-
dc.identifier.wosid000259133100005-
dc.identifier.scopusid2-s2.0-49549123141-
dc.type.rimsART-
dc.citation.volume41-
dc.citation.issue3-
dc.citation.beginningpage188-
dc.citation.endingpage205-
dc.citation.publicationnameCOMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS-
dc.identifier.doi10.1016/j.comgeo.2007.12.001-
dc.contributor.localauthorCheong, Otfried-
dc.contributor.nonIdAuthorHaverkort, Herman-
dc.contributor.nonIdAuthorLee, Mira-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorspanner-
dc.subject.keywordAuthordilation-
dc.subject.keywordAuthoroptimization-
dc.subject.keywordAuthorspanning tree-
dc.subject.keywordAuthorgeometric network-
dc.subject.keywordAuthorNP-hardness-
dc.subject.keywordPlusPLANAR GRAPHS-
dc.subject.keywordPlusSPANNERS-
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
000259133100005.pdf(259.23 kB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 12 items in WoS Click to see citing articles in records_button

Display Simple Item Record

qr_code

  • mendeley

    citeulike

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


rss_1.0 rss_2.0 atom_1.0