크기 2n×2m 인 메쉬의 꼬인 큐브에 대한 임베딩 = Embedding a Mesh of Size 2n×2m Into a Twisted Cube

국문 초록 (Abstract)

하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 2 × 2m인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 4× 2m인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m이 짝수일 경우엔 크기 2ⁿ × 2m인 메쉬가 꼬인 큐브에 연장율 1, 확장율 2n?1로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 2ⁿ로 임베딩됨을 보인다 (1≤n≤m).

다국어 초록 (Multilingual Abstract)

The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m , a mesh of size 2× 2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 4 × 2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2ⁿ × 2m can be embedded into a twisted cube with dilation 1 and expansion 2n?1 for even m and with dilation 1 and expansion 2n for odd m where 1≤ n ≤ m.