Optimal Layouts of Virtual Paths in Complete Binary Tree Networks

Suguru AMITANI  Toshinori YAMADA  Shuichi UENO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.4   pp.914-917
Publication Date: 2002/04/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
communication network,  complete binary tree network,  congestion,  hop number,  

Full Text: PDF>>
Buy this Article

It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.