스타 그래프와 팬케익, 버블정렬 그래프 사이의 임베딩 알고리즘 = Embedding algorithm among star graph and pancake graph, bubblesort graph

국문 초록 (Abstract)

스타 그래프는 노드 대칭성, 최대 고장 허용도, 계층적 분할 성질을 갖고, 하이퍼큐브보다 망 비용이 개선된 널리 알려진 상호 연결망이다. 본 연구에서는 스타 그래프와 그의 변형된 그래프들 상호 간의 임베딩 방법을 제안한다. 버블정렬 그래프가 팬케익 그래프와 스타 그래프에 각각 연장율 3, 확장율 1로 임베딩 가능함을 보이고, 팬케익 그래프가 버블정렬그래프에 임베딩 하는 연장율 비용이 O(n2)임을 보인다. 그리고 스타 그래프가 팬케익 그래프에 연장율 4, 확장율 1로 임베딩 가능함을 보인다. 또한 스타그래프를 버블정렬 그래프에, 팬케익 그래프를 스타 그래프에 임베딩 하는 연장율 비용이 각각 O(n)임을 보인다.

다국어 초록 (Multilingual Abstract)

Star graph is a well-known interconnection network to further improve the network cost of Hypercube and has good properties such as node symmetry, maximal fault tolerance and strongly hierarchical property. In this study, we will suggest embedding scheme among star graph and pancake graph, bubblesort graph, which are variations of star graph. We will show that bubblesort graph can be embedded into pancake and star graph with dilation 3, expansion 1, respectively and pancake graph can be embedded into bubblesort graph with dilation cost O(n2). Additionally, we will show that star graph can be embedded into pancake graph with dilation 4, expansion 1. Also, with dilation cost O(n) we will prove that star graph can be embedded into bubblesort graph and pancake graph can be embedded into star graph.

참고문헌 (Reference)

1 김종석, "상호연결망 폴디드 하이퍼-스타 FHS(2n,n)의 대칭성과 임베딩 알고리즘" 한국정보처리학회 16 (16): 501-508, 2009

2 김종석, "계층적 폴디드 하이퍼스타 네트워크의 임베딩 알고리즘" 한국정보처리학회 16 (16): 299-306, 2009

3 Latifi, S., "Transposition networks as a class of fault- tolerant robust networks" 45 (45): 230-238, 1996

4 Akers, S. B., "The star graph: an attractive alternative to the n-cube" 393-400, 1987

5 Suzuki, Y., "The container problem in bubble-sort graphs" E91-D(4), : 1003-1009, 2008

6 Sawada, N., "Pairwise Disjoint Paths in Pancake Graphs" 376-382, 2007

7 Fan, J., "Optimal embedding of paths with various lengths in twisted cubes" 18 (18): 511-521, 2007

8 Mendia, V. E., "Optimal broadcasting on the star Graph" 3 (3): 389-396, 1992

9 Shen, X., "On embedding between 2d meshes of the same size" 46 (46): 880-889, 1997

10 Yeh C. H., "Macro-star networks: efficient low-degree alternatives to star graphs" 9 (9): 987-1003, 1998

11 Araki, T., "Hamiltonian laceability of bubble-sort graphs with edge faults" 177 (177): 2679-2691, 2007

12 Bettayeb, S., "Embedding star networks into hypercubes" 45 (45): 186-194, 1996

13 Lin, J.-C., "Embedding of complete binary tree with 2-expansion in a faulty flexible hypercube" 47 (47): 543-548, 2001

14 Hamdi, M., "Embedding hierarchical hypercube networks into the hypercube" 8 (8): 897-902, 1997

15 Tsai, P.-Y., "Edge-fault-tolerant hamiltonicity of pancake graphs under the conditional fault model" 409 : 450-460, 2008

16 Chou, Z.-T., "Bubblesort star graphs: a new interconnection network" 41-48, 1996

17 Akers, S. B., "A group-theoretic model for symmetric interconnection network" 38 (38): 555-565, 1989