Efficient dynamic embedding of arbitrary binary trees into hypercubes

In this paper, a deterministic algorithm for dynamically embedding binary trees into next to optimal hypercubes is presented. Due to a known lower bound, any such algorithm must use either randomization or migration, i.e., remapping of tree vertices, to obtain an embedding of trees into hypercubes with small dilation, load, and expansion simultaneously. The algorithm presented here uses migration of previously mapped tree vertices and achieves dilation 9, unit load, expansion <4 and constant node-congestion. Moreover, the embedding can be computed on the hypercube. The amortized time for each new vertex is constant, if in each step one new leaf is spawned. If in each step a group of Mnew leaves is added, the amortized cost for each new group of leaves is bounded by O(log²(M)).