기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
완전이진트리의 교차큐브에 대한 임베딩
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 완전이진트리의 교차큐브에 대한 임베딩
저자명
김숙연,Kim. Sook-Yeon
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2009년|36권 3호|pp.149-157 (9 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

교차큐브는 하이퍼큐브의 변형으로서 하이퍼큐브의 절반정도의 지름을 가지는 등의 개선된 망 성질을 가진다. N-노드 완전이진트리는 (N+1)-노드 교차큐브의 부그래프임이 알려져 있으나 [P. Kulasinghe and S, Bettayeb, 1995] 완전이진트리의 노드 개수가 교차큐브의 노드 개수보다 더 큰 경우에 대한 효과적인 임베딩 방법은 알려져 있지 않다. 본 논문에서는 N-노드 완전이진트리를 N-노드 교차큐브에 연장을 1, 부하율 [N/M]로 임베딩할 수 있음을 보인다(N>M$geq$2). 여기서 연장율과 부하율은 최적이다. 본 논문에서 제시하는 임베딩 방법은 같은 레벨의 트리 노드들을 교차큐브의 노드들에 골고루 분포시키는 특징도 가지고 있다. 이 특징은 트리 구조 알고리즘을 교차큐브에서 레벨 단위로 실행할 때 특히 유용하다.

기타언어초록

The crossed cube, a variation of the hypercube, possesses a better topological property than the hypercube in its diameter that is about half of that of the hypercube. It has been known that an N-node complete binary tree is a subgraph of an (N+1)-node crossed cube [P. Kulasinghe and S. Bettayeb, 1995]. However, efficient embedding methods have not been known for the case that the number of nodes of the complete binary tree is greater than that of the crossed cube. In this paper, we show that an N-node complete binary tree can be embedded into an M-node crossed cube with dilation 1 and load factor [N/M], N>M$geq$2. The dilation and load factor is optimal. Our embedding has a property that the tree nodes on the same level are evenly distributed over the crossed cube nodes. The property is especially useful when tree-structured algorithms are processed on a crossed cube in a level-by-level way.