DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Chwa, Kyung-Yong | - |
dc.contributor.advisor | 좌경룡 | - |
dc.contributor.author | Park, Yong-Hee | - |
dc.contributor.author | 박용희 | - |
dc.date.accessioned | 2011-12-13T06:04:58Z | - |
dc.date.available | 2011-12-13T06:04:58Z | - |
dc.date.issued | 2005 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=243819&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/34658 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전산학전공, 2005.2, [ vi, 25 p. ] | - |
dc.description.abstract | An important feature of an interconnection network is its ability to efficiently simulate algorithms proposed for other architectures. Such a simulation problem can be formulated as graph embedding. A good embedding is said to exist when adjacent vertices in the guest graph are mapped to reasonably close vertices in the host graph and when a path between adjacent vertices in the guest graph is chosen in a way that the congestion of the corresponding path in the host graph is moderately small. Therefore, the fitness of embedding can be measured by dilation and congestion. In this thesis, we embed grids into recursive circulant. Recursive circulant R(N, d) is a circulant graph with N vertices and jumps of power of d. We propose an embedding scheme named iterative 2-edge labeling which can embed 88.6% of grids into their optimal recursive circulant with dilation 1 and congestion 1. This algorithm also can be applied for embedding cylinder and torus into recursive circulant. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Grid | - |
dc.subject | Recursive Circulant | - |
dc.subject | Embedding | - |
dc.subject | 2-edge Labeling | - |
dc.subject | 2-에지 라벨링 | - |
dc.subject | 격자 | - |
dc.subject | 재귀 원형군 | - |
dc.subject | 임베딩 | - |
dc.title | Embedding grids into recursive circulants using iterative 2-edge labeling | - |
dc.title.alternative | 연속 라벨링을 이용한 재귀 원형군에서의 격자구조 임베딩 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 243819/325007 | - |
dc.description.department | 한국과학기술원 : 전산학전공, | - |
dc.identifier.uid | 020033260 | - |
dc.contributor.localauthor | Chwa, Kyung-Yong | - |
dc.contributor.localauthor | 좌경룡 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.