Link-disjoint embedding of complete binary trees in meshes
Sang-Kyu Lee, Hyeong‐Ah Choi · Networks · 1997
We consider the problem of embedding complete binary trees into meshes with the objective of minimizing the link congestion. Gibbons and Paterson showed that a complete binary tree Tp (with 2p − 1 nodes) can be embedded into a 2-dimensional mesh of 2p nodes with link congestion two. Using the dimension-ordered routing, the authors showed that Tp can be embedded into a 2-dimensional mesh of (81/64)2p nodes with link congestion one and mesh of 2p nodes with link congestion two. This paper shows that the increase of the dimension of a mesh gives a better embedding. In particular, Tp can be embedded into a 3-dimensional mesh with 2p nodes such that the link congestion of each dimension is two, two, and one if the dimension-ordered routing is used and two, one, and one if the dimension-ordered routing is not imposed. For a 4-dimensional mesh of 2p nodes, we show that Tp can be embedded with link congestion one in each dimension if p = 4k for an integer k. © 1997 John Wiley & Sons, Inc. Networks 30: 283–292, 1997