DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Chwa, Kyung-Yong | - |
dc.contributor.advisor | 좌경룡 | - |
dc.contributor.author | Kim, Sook-Yeon | - |
dc.contributor.author | 김숙연 | - |
dc.date.accessioned | 2011-12-13T05:24:23Z | - |
dc.date.available | 2011-12-13T05:24:23Z | - |
dc.date.issued | 1998 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=134779&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/33101 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전산학과, 1998.2, [ [104] p. ] | - |
dc.description.abstract | Graph embedding is one of the key conceptual tools for implementing parallel algorithms or simulating interconnection networks on a parallel computer. In this thesis, we study on embeddings of graphs into a hypercube, recursive circulant, and hypermesh. First, we propose a many-to-one embedding strategy of a tree-related graph into a recursively-structured graph. Here, the tree related graph is a complete binary tree, mesh of trees or pyramid. The strategy evenly distributes the same level nodes of a tree-related graph to the nodes of the recursively-structured graph. From this strategy, we design embedding methods of a tree-related graph into a hypercube or recursive circulant. The methods are optimal or nearly optimal in terms of the general embedding measures such as dilation, congestion, and load. Second, we present one-to-one embedding methods of graphs into a hypermesh. All these embeddings are optimal in terms of alignment cost. The alignment cost is one of the important embedding measures for hypermesh. We show how to embed a butterfly using the concept of quotient group. We also show how to embed multiple copies of a graph using a labeling scheme. This embedding of multiple copies is optimal in all respects of congestion, expansion, and alignment cost. Our new or improved embedding results shows that the recursive circulant and hypermesh as well as the hypercube are versatile interconnection networks. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Recursive circulant | - |
dc.subject | Hypermesh | - |
dc.subject | Hypercube | - |
dc.subject | Graph embedding | - |
dc.subject | Labeling | - |
dc.subject | 레이블링 | - |
dc.subject | 제귀원형군 | - |
dc.subject | 하이퍼메쉬 | - |
dc.subject | 하이퍼큐브 | - |
dc.subject | 그래프 임베딩 | - |
dc.title | Graph embedding into recursively-structured graphs and hypermeshes | - |
dc.title.alternative | 재귀구조 그래프들과 하이퍼메쉬들에 대한 그래프 임베딩 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 134779/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 000935056 | - |
dc.contributor.localauthor | Chwa, Kyung-Yong | - |
dc.contributor.localauthor | 좌경룡 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.