Embedding complete binary trees into parity cubes
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 1-27 |
| Journal / Publication | Journal of Supercomputing |
| Volume | 71 |
| Issue number | 1 |
| Publication status | Published - 2014 |
Link(s)
Abstract
The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The parity cube is an important variant of the hypercube. It has many attractive features superior to those of the hypercube. In this paper, we prove that the complete binary tree with (Formula Presented.) vertices can be embedded with dilation 1, congestion 1, load 1 into the n-dimensional parity cube (Formula Presented.) and expansion tending to 1. Furthermore, we provide an (Formula Presented.) algorithm to construct the complete binary tree with (Formula Presented.) vertices in (Formula Presented.), where (Formula Presented.) denotes the number of vertices in (Formula Presented.) and (Formula Presented.).
Research Area(s)
- Complete binary tree, Congestion, Dilation, Embedding, Expansion, Interconnection architecture, Load, Parity cube
Citation Format(s)
Embedding complete binary trees into parity cubes. / Liu, Zhao; Fan, Jianxi; Jia, Xiaohua.
In: Journal of Supercomputing, Vol. 71, No. 1, 2014, p. 1-27.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
