상호연결망 폴디드 하이퍼-스타 연결망 FHS(2n,n)의 고장 지름
Fault Diameter of Folded Hyper-Star Interconnection Networks FHS(2n,n)
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
고장 지름은 상호연결망의 통신 능률과 신뢰도를 평가하는 중요한 척도 중의 하나이다. 이형옥 외 4인[Folded 하이퍼-스타 그래프의 병렬 경로, 한국정보처리학회논문지, Vol.6, No.7, pp.1756-1769, 1999]은 폴디드 하이퍼-스타 FHS(2n,n)의 노드 중복 없는 경로를 제안하였고, FHS (2n,n)의 고장 지름이 2n-1 이하임을 증명하였다. 본 논문에서는 폴디드 하이퍼-스타 FHS(2n,n)의 개선된 노드 중복 없는 경로를 제안한다. 그리고 FHS(2n,n)의 광역 지름이 dist(U,V)+4이고, 고장 지름이 n+2 이하임을 증명한다.
Abstract
The fault diameter is one of the important measures for transmission rate and reliability of interconnection network. H.-O. Lee et al.[Parallel paths in folded hyper-star graph, Journal of KIPS, Vol.6, No.7, pp.1756-1769, 1999] suggested the node-disjoint paths of FHS (2n,n), and proved that the fault diameter of FHS(2n,n) is less than 2n-1. In this paper, we suggest an advanced node-disjoint paths of FHS(2n,n). We also prove that the wide diameter of FHS(2n,n) is dist(U,V)+4, and the fault diameter of FHS(2n,n) is less than n+2.
참고문헌 (20)
- C.-P. Chang, "Edge Congestion and Topological Properties of Crossed Cubes", IEEE Trans. Parallel and Distributed Systems, 11(1), pp.64~80 (2000)
- E. Cheng, "Structural properties of hyperstars", Ars Combinatoria, 80, pp.65~73 (2006)
- E. Cheng, "A strong structural theorem for hyper-stars", Congressus Numerantium, 179, pp.181~191 (2006)
- D.-R. Duh, "Algorithms and properties of a new two-level network with folded hypercubes as basic modules", IEEE Trans. Parallel and Distributed Systems, 6(7), pp.714~723 (1995)
- K. Day, "Fault diameter of k-ary n-cube networks", IEEE Trans. Parallel and Distributed Systems, 8(9), pp.903~907 (1997)
- J.-S. Fu, "Node-disjoint paths and related problems on hierarchical cubic networks", Networks, 40(3), pp.142~154 (2002)
- D.F.Hsu, "On container width and length in graphs, groups, and networks", IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences, 77, pp.668~680 (1994)
- J.-S. Kim, "Embedding hypercubes,rings and odd graphs into Hyper-stars", International Journal of Computer Mathematics, 86(5), pp.771~778 (2009)
- J.-S. Kim, "Comments on A Study of Odd Graphs as Fault-Tolerant Interconnection Networks", IEEE Transactions on Computers, 57(6), pp.864~ (2008)
- S.Latifi, "Combinatorial Analysis of the Fault-Diameter of the n-cube", IEEE. Trans. Computers, 42(1), pp.27~33 (1993)
- 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)
- Y. Rouskov, "Fault diameter of star graphs", Information Processing Letters, 48(5), pp.243~251 (1993)
- M. Xu, "Fault diameter of Cartesian product graphs, Infomation Processing Letters", 93(5), pp.245~248 (2005)
- 김종석, "하이퍼-스타 연결망의 위상적 성질과 방송 알고리즘", 정보처리학회논문지A, 11(6), pp.341~346 (2004), 한국정보처리학회
- 김종석, "상호연결망 하이퍼-스타 HS(2n,n)의 이분할 에지수와 고장지름 분석", 정보처리학회논문지A, 12(7), pp.499~506 (2005), 한국정보처리학회
- 김종석, "PMC 모델과 비교진단 모델을 이용한 하이퍼-스타 연결망의 진단도 분석", 정보처리학회논문지A, 13(1), pp.19~26 (2006), 한국정보처리학회
- 김종석, "Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석", 정보처리학회논문지A, 14(5), pp.263~268 (2007), 한국정보처리학회
- 김종석, "상호연결망 폴디드 하이퍼-스타 FHS(2n,n)의 대칭성과 임베딩 알고리즘", 정보처리학회논문지A, 16(6), pp.501~508 (2009), 한국정보처리학회
- 이형옥, "하이퍼-스타 그래프 : 다중 컴퓨터를 위한 새로운 상호 연결망", 한국정보처리학회논문지, 5(12), pp.3099~3108 (1998)
- 이형옥, "Folded 하이퍼-스타 그래프의 병렬 경로", 한국정보처리학회논문지, 6(7), pp.1756~1769 (1999)