Premium
Link‐disjoint embedding of complete binary trees in meshes
Author(s) -
Lee SangKyu,
Choi HyeongAh
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199712)30:4<283::aid-net5>3.0.co;2-f
Subject(s) - polygon mesh , link (geometry) , embedding , disjoint sets , dimension (graph theory) , routing (electronic design automation) , computer science , binary tree , combinatorics , mathematics , binary number , integer (computer science) , topology (electrical circuits) , computer network , geometry , arithmetic , artificial intelligence , programming language
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 T p (with 2 p − 1 nodes) can be embedded into a 2‐dimensional mesh of 2 p nodes with link congestion two. Using the dimension‐ordered routing, the authors showed that T p can be embedded into a 2‐dimensional mesh of (81/64)2 p nodes with link congestion one and mesh of 2 p nodes with link congestion two. This paper shows that the increase of the dimension of a mesh gives a better embedding. In particular, T p can be embedded into a 3‐dimensional mesh with 2 p 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 2 p nodes, we show that T p can be embedded with link congestion one in each dimension if p = 4 k for an integer k . © 1997 John Wiley & Sons, Inc. Networks 30: 283–292, 1997