Efficient Dynamic Embeddings of Binary Trees into Hypercubes

In this paper, a deterministic algorithm for dynamically embedding binary trees into hypercubes is presented. Because of 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. Using migration of previously mapped tree vertices, the presented algorithm constructs a dynamic embedding which achieves dilation of at most 9, unit load, nearly optimal expansion, and constant edge- and node-congestion. This is the first dynamic embedding that achieves these bounds simultaneously. Moreover, the embedding can be computed efficiently on the hypercube itself. The amortized time for each spawning step is bounded by O(log^2(L)), if in each step at most L new leaves are spawned. From this construction, a dynamic embedding of large binary trees into hypercubes is derived which achieves dilation of at most 6 and nearly optimal load. Similarly, this embedding can be constructed with nearly optimal load q on the hypercube itself in amortized time O(q log^2(L/q)) per spawning step, if in each step at most L new leaves are added.

ICSI Technical Report TR-98-023

Technical Report