초록 close

본 논문에서는 최근에 제안된 상호연결망 (n,k)-스타 그래프에서 결함 노드를 포함하는 경우의 링 임베딩 문제를 다룬다. 그래프 자체의 계층적 특성을 이용한 일련의 차원 확장 및 결함 노드의 분산 전략을 효율적으로 이용하여 n-3개 이하의 결함 노드만을 포함하고 n-k 2를 만족하는 (n,k)-스타 그래프에서 고장 노드들만 제외시킨 최대 크기의 링을 임베딩할 수 있음을 보이고 해당 임베딩 알고리즘을 제시한다.본 논문에서 다루고 있는 사이클 특성과 관련된 링 임베딩 연구는 병렬처리 분야에서의 멀티캐스팅 등과 같이 내재된 사이클 특성을 활용하는 분야에 응용이 가능하다.


In this paper, we consider ring embedding problem in faulty (n,k)-star graphs which is recently proposed as an alternative interconnection network topology. By effectively utilizing such strategies as a series of dimension expansions and even distribution of faulty nodes into sub-stars in graph itself, we prove that it is possible to construct a maximal fault-free ring excluding only faulty nodes when the number of faults is no more than n-3 and n-k 2, and also propose an algorithm which can embed the corresponding ring in (n,k)-star graphs. This result will be applied into the multicasting applications that use the underlying cycle properties on the multi-computer system.