Congestion-free, dilation-2 embedding of complete binary trees into star graphs

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 期刊論文 > Item 987654321/29147

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/29147

题名:	Congestion-free, dilation-2 embedding of complete binary trees into star graphs
作者:	Tseng,YC;Chen,YS;Juang,TY;Chang,CJ
贡献者:	資訊工程研究所
关键词:	INTERCONNECTION NETWORK
日期:	1999
上传时间:	2010-06-29 20:14:50 (UTC+8)
出版者:	中央大學
摘要:	Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilation-2, load-1 embedding of a level-p binary tree, and (ii) a congestion-free, dilation-2, load-2(k) embedding of a level-(p + k) binary tree, into an n-dimensional star graph, where p = Sigma(i=2)(n) [log i] = Omega(n log n) and k is any positive integer. The first result offers a tree of size comparable or superior to existing results, but with less congestion and dilation. The second result provides more flexibility in the embeddable tree sizes compared to existing results. (C) 1999 John Wiley & Sons, Inc.
關聯:	NETWORKS
显示于类别:	[資訊工程研究所] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	378	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing