Minimum Congestion Embedding of Complete Binary Trees into Tori

概要

論文の詳細を見る
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-1-vertex 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-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.
一般社団法人電子情報通信学会の論文
2000-09-25