매크로-스타 그래프와 행렬 스타 그래프 사이의 임베딩 = Embedding between a Macro-Star Graph and a Matrix Star Graph

다국어 초록 (Multilingual Abstract)

A Macro-Star graph which has a star graph as a basic module has node symmetry, maximum fault tolerance, and hierarchical decomposition property. And, it is an interconnection network which improves a network cost against a star graph. a matrix star graph also has such good properties of a Macro-Star graph and is an interconnection network which has a lower network cost than a Macro-Star graph. In this paper, we propose a method to embed between a Macro-Star graph and a matrix star graph. We show that a Macro-Star graph MS(k,n) can be embedded into a matrix star graph MSk,n 1 with dilation 2. In addition, we show that a matrix star graph MSk,n can be embedded into a Macro-Star graph MS(k,n 1) with dilation 4 and average dilation 3 or less as well. This result means that several algorithms developed in a star graph can be simulated in a matrix star graph with constant cost.