상호연결망 하이퍼-스타 HS(2n,n)의 이분할 에지수와 고장지름 분석
Analysis of Bisection width and Fault Diameter for Hyper-Star Network HS(2n,n)
0
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
최근에 하이퍼큐브의 망비용을 개선한 하이퍼-스타 연결망 HS(m,k)이 제안되었다. 본 논문에서는 정규연결망 하이퍼-스타 HS(2n,n)의 이분할 에지수가 최대 임을 보이고, 병렬경로 집합을 이용하여 k-광역지름이 dist(u,v)+4이하이고, HS(2n,n)의 고장지름이 D(HS(2n,n))+2 이하임을 보인다. dist(u,v)는 임의의 두 노드 u와 v 사이의 최단 거리를 나타내고, D(HS(2n,n))는 HS(2n,n)의 지름을 나타낸다.
Abstract
Recently, Hyper-Star network HS(m,k) which improves the network cost of hypercube has been proposed. In this paper, we show that the bisection width of regular Hyper-Star network HS(2n,n) is maximum . Using the concept of container, we also show that k-wide diameter of HS(2n,n) is less than dist(u,v)+4, and the fault diameter is less than D(HS(2n,n))+2, where dist(u,v) is the shortest path length between any two nodes u and v in HS(2n,n), and D(HS(2n,n)) is its diameter.
참고문헌 (13)
- "Edge Congestion and Topological Properties of Crossed Cubes", 11(1), pp.64~80 (2000)
- "On the diameter vulnerability of Kautz digraphs", 151, pp.81~85 (1996)
- "On the Rabin number problem", 30, pp.219~230 (1997)
- "A Note on Recursive Cube of Rings Network", 16(10), pp.1007~1008 (2005)
- "A Counterexample to Tang and Padubidri's Claim about the bisection width of a Diagonal Mesh", 52(5), pp.676~677 (2003)
- "Fault diameter of interconnection networks", 13(5-6), pp.577~582 (1987)
- "Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube", LNCS 2510, pp.858~865 (2002)
- "Introduction to Parallel Algorithms and Architectures" (1992), Morgan Kaufmann Publishers
- "Fault-tolerant routing in circulant networks and cycle prefix networks", 2(5-6), pp.165~172 (1998)
- "Optimal Broadcasting on the Star Graph", 3(4), pp.389~396 (1992)
- B. Parhami, "Perfect Difference Networks and Related Interconnection Structures for Parallel and Distributed Systems", 16(8), pp.714~724 (2005)
- K.W. Tang, "Diagonal and Toroidal Mesh Networks", 43(7), pp.815~826 (1994)
- "하이퍼-스타 연결망의 위상적 망성질과 방송 알고리즘", 11-=A(5), pp.341~346 (2004)