초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

It has been shown that the star graph is an interconnection network which has many useful properties of the hypercube and is superior to the hypercube in some cases. Although the star graph has many attractive properties as a multiprocessor interconnection network, few algorithms exist to show its p...

It has been shown that the star graph is an interconnection network which has many useful properties of the hypercube and is superior to the hypercube in some cases. Although the star graph has many attractive properties as a multiprocessor interconnection network, few algorithms exist to show its potential. In this paper two algorithms for embedding a complete binary tree in the star graph having n¹ nodes are described. Our algorithms give two embeddings with dilation 1 and expansion n¹/(2 ⁿ-1-1) and with dilation 2 and expansion n¹/(2^m-l), respectively, where m=nㆍ[log n]-2ㆍ2^([log n])+3 No algorithm for embedding a complete binary tree in the star graph has been reported yet Our embedding results are better than the one obtained by embedding a complete binary tree in a hypercube and embedding the resulting hypercube in the star graph.