Minimum Congestion Embedding of Complete Binary Trees into Tori
Akira Matsubayashi, Ryo Takasu · Institutional Repositories DataBase (IRDB) · 2000
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 2 n -1vertex complete binary tree can be embedded in a (2 n/2 + 1) × (2 n/2 +1)-grid and a 2 n/2 ×2 n/2 -grid with congestion 1 and 2, respectively.However, it is not known if 2 n -1-vertex complete binary tree is embeddable in a 2 n/2 × 2 n/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 2 n -1-vertex complete binary tree can be embedded with unit congestion in a 2 n/2 × 2 n/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 2 n -1vertex complete binary tree with an even integer n into a square torus with unit congestion.