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.
