완전 이진 트리의 재귀 원형군에 대한 Embedding

김숙연, 박정흠, 좌경룡 · 한국정보과학회 학술발표논문집 · 1992

본 논문에서는 divide and conquer 알고리즘을 효율적으로 수행할 수 있는 병렬구조인 완전 이진 트리를 최근에 [4]에서 제안한 병렬 컴퓨터 구조 재귀 원형군(recursive circulant) 에 다대일 embedding하는 문제를 다룬다. 레벨 n인 완전 이진 트리 T_n을 재귀 원형군 G(2^m,4), 1 ≤m≤n-1,에 load factor 가 최적 일때, dilation 2, congestion 2로 embedding할 수 있고 load factor가 최적 load factor+1일때, dilation 1, congestion 2로 embedding할 수 있음을 보인다. 이 결과를 완전 이진 트리에 에지가 첨가된 X-트리나 full ringed 트리에 확장하면 그것들도 load factor 2, dilation 2로 embedding될 수 있다.

Cited by 1 works.

Authors