For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Minimum Congestion Embedding of Complete Binary Trees into Tori
Akira MATSUBAYASHI Ryo TAKASU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/09/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph embedding, congestion, complete binary tree, torus,
Full Text: PDF(952.7KB)>>
We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2n-1-vertex complete binary tree can be embedded in a (2n/2+1)(2n/2+1)-grid and a 2n/2 2n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2n-1-vertex complete binary tree is embeddable in a 2n/2 2n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2n-1-vertex complete binary tree can be embedded with unit congestion in a 2n/2 2n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2n-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.