TY - JOUR
T1 - Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
AU - Heun, Volker
AU - Mayr, Ernst W.
PY - 2001/8
Y1 - 2001/8
N2 - It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Because of the similarity, our results can be immediately transfered to complete binary trees.
AB - It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Because of the similarity, our results can be immediately transfered to complete binary trees.
KW - Dynamic embedding; complete binary tree; hypercube; simulation of algorithms
UR - http://www.scopus.com/inward/record.url?scp=0242327279&partnerID=8YFLogxK
U2 - 10.1006/jpdc.2001.1734
DO - 10.1006/jpdc.2001.1734
M3 - Article
AN - SCOPUS:0242327279
SN - 0743-7315
VL - 61
SP - 1110
EP - 1125
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 8
ER -