Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into
Hypercubes
The double-rooted complete binary tree is a complete binary tree
where the path (of length 2) between the children of the root is replaced
by a path of length 3.
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 the hypercube does not provide any hint 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 and, therefore, of complete binary trees into
hypercubes which do not suffer from this disadvantage.
We also give an edge-disjoint embedding with optimal load 2 and unit
dilation such that each hypercube vertex is an image of at most one
vertex of a level.
Moreover, 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.
Since complete binary trees are similar to doube-rooted complete binary
trees, we can transfer our results immediately to complete binary trees.
