DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Cheong, Otfried | - |
dc.contributor.advisor | Haverkort, Herman | - |
dc.contributor.advisor | 정지원 | - |
dc.contributor.author | Lee, Mi-Ra | - |
dc.contributor.author | 이미라 | - |
dc.date.accessioned | 2011-12-13T06:06:42Z | - |
dc.date.available | 2011-12-13T06:06:42Z | - |
dc.date.issued | 2007 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=265052&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/34771 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전산학전공, 2007.2, [ v, 31 p. ] | - |
dc.description.abstract | In a geometric network G=(S,E), the graph distance between two vertices u, v∈S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which graph distance differs from the Euclidean distance between every pair of vertices. We show that given a set S of n points and a dilation $\delta$>1, it is NP-hard to determine whether a spanning tree of S with dilation at most $\delta$ exists. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Dilation | - |
dc.subject | Graph | - |
dc.subject | Computational Geometry | - |
dc.subject | NP-hard | - |
dc.subject | NP-hard | - |
dc.subject | Dilation | - |
dc.subject | 그래프 | - |
dc.subject | 계산기하 | - |
dc.title | Computing a minimum-dilation spanning tree is NP-hard | - |
dc.title.alternative | 최소-Dilation 신장 트리 찾기의 NP-hard 증명 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 265052/325007 | - |
dc.description.department | 한국과학기술원 : 전산학전공, | - |
dc.identifier.uid | 020053955 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.localauthor | Haverkort, Herman | - |
dc.contributor.localauthor | 정지원 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.