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

• 영문명: A Searching Algorithm for Shortest Path in RCR Network
• 발행기관: 한국전자통신학회
• 저자명: 김성열(Seong-yeol Kim)
• 간행물 정보: 『한국전자통신학회 논문지』제5권 제5호, 444~448쪽, 전체 5쪽
• 주제분류: 공학 > 전자/정보통신공학
• 파일형태: PDF
• 발행일자: 2010.10.30

국문 초록

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

영문 초록

RCR network[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 algorithm for finding next node on a shortest path.

목차

I. Introduction

II. Condition for Being A Connected Graph

III. New Definition of Network Diameter

IV. Algorithm for Finding Next Node on A Shortest Path

Ⅴ. Conclusion

References

키워드

RCR(Recursive Cube of Rings) Connected graph Network diameter Shortest Path