RCR 네트워크에서 최단경로 탐색 알고리즘

• 영문명: An Algorithm for Finding Shortest Path in RCR Network
• 발행기관: 한국전자통신학회
• 저자명: 김성열(Seong yeol Kim)
• 간행물 정보: 『한국전자통신학회 학회지』제4권 제1호, 79~82쪽, 전체 4쪽
• 주제분류: 공학 > 전자/정보통신공학
• 파일형태: PDF
• 발행일자: 2010.07.26

국문 초록

Y.Sun[1]이 제안한 RCR 네트워크 토폴로지는 짧은 지름, 대칭성 등 병 렬컴퓨팅 환경을 구성하기 위한 특성을 가진 상호연결망의 일종이다. Hu and Cao[2]에 의해 이 토폴로지 분석에 대한 재검토가 이루어졌는데, 그래프 비연결성, 직경, bisection width 등에 대한 오류가 있음이 지적되었다. 이 연구에서는 RCR 네트워크 토폴로지 특성을 분석하고 [2]의 결과에도 여전히 남아있는 '연결그래프가 되기 위한 조건' 및 직경에 대한 오류를 정정한다. 그리고 RCR 네 트워크에서 최단경로를 구하기 위한 알고리즘을 제안한다.

영문 초록

RCR net:work[1] is a topology for interconnection networks having many desirable properties for building scalable parallel machines. This had been analyzed by Hu and Cao[2] to deal with problems of disconnected graph, bisection width and diameter. We analyze some properties of RCR again and revise the condition for connected graph and network diameter. And we present an efficient algoritlun for finding next node on a shortest path.

목차

요약

Abstract

Ⅰ. INTRODUCTION

Ⅱ. CONDITION FOR BEING A CONNECTED GRAPH

Ⅲ. NEW DEFINITION OF NETWORK DIAMETER

Ⅳ. ALGORITHM FOR FINDING NEXT NODE ON A SHORTEST PATH

Ⅴ. Conclusion

REFERENCES

키워드

Recursive Cube of Rings(RCR) Connected graph Network diameter