하이퍼스타 연결망 HS(2n,n)의 에지 중복 없는 최적 스패닝 트리
Optimal Edge-Disjoint Spanning Trees in HyperStar Interconnection Network HS(2n,n)
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최근에 병렬처리를 위한 새로운 위상으로 하이퍼‐스타 연결망 HS(2n,n)가 제안되었다. 하이퍼‐스타 연결망은 하이퍼큐브와 스타 그래프의 성질을 가지고 있으면서, 같은 노드수를 갖는 하이퍼큐브보다 망비용이 우수한 연결망이다. 본 논문에서는 하이퍼스타 연결망 HS(2n,n)에서 에지 중복 없는 스패닝 트리를 구성하는 알고리즘을 제안한다. 그리고 제안한 알고리즘에 의해 구성된 에지 중복 없는 스패닝 트리가 에지 중복 없는 최적 스패닝 트리임을 증명한다.
Abstract
Recently, a HyperStar network HS(2n,n) has been introduced as a new interconnection network of new topology for parallel processing. HyperStar network has properties of hypercube and star graph, further improve the network cost of a hypercube with the same number of nodes. In this paper, we show a construction algorithm of edge-disjoint spanning trees in HyperStar network HS(2n,n). Also, we prove that edge-disjoint spanning tree by the algorithm is optimal.
참고문헌 (12)
- E. Cheng, "Structural properties of hyper-stars", Ars Combinatoria, 80, pp.65~73 (2006)
- E. Cheng, "A strong structural theorem for hyper-stars", Congressus Numerantium, 179, pp.181~191 (2006)
- P. Fragopoulou, "Edge-disjoint spanning trees on the star network with applications to fault tolerance", IEEE Trans. Computers, 45(2), pp.174~185 (1996)
- P. Fraigniaud, "Arc-disjoint spanning trees on the cube connected cycles network", Proc. International Conference on Parallel Processing, 1, pp.225~229 (1991)
- S.L. Johnson, "Optimal broadcasting and personalized communication in hypercubes", IEEE Trans. Computers, 38(9), pp.1249~1268 (1989)
- J.-S. Kim, "Embedding hypercubes, rings and odd graphs into Hyper-stars", International Journal of Computer Mathematics
- H.-O. Lee, "Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube", Lecture Notes in Computer Science : EurAsia-ICT 2002, pp.858~865 (2002)
- C.-T. Lin, "Embedding k(n-k) edge-disjoint spanning trees in arrangement graphs", J. Parallel and Distributed Computing, 63, pp.1277~1287 (2003)
- W. Shi, "One to all broadcast in hyper butterfly networks", International Conference on High Performance Computing, pp.155~162 (1998)
- 김종석, "하이퍼-스타 연결망의 위상적 망성질과 방송 알고리즘", 정보처리학회논문지A, 11-A(5), pp.341~346 (2004)
- 김종석, "상호연결망 하이퍼-스타 HS(2n,n)의 이분할 에지수와 고장지름 분석", 정보처리학회논문지 A B C D, 12(7), pp.499~506 (2005), 한국정보처리학회
- 김종석, "PMC 모델과 비교진단 모델을 이용한 하이퍼-스타 연결망의 진단도 분석", 정보처리학회논문지 A B C D, 13(1), pp.19~26 (2006), 한국정보처리학회