TY - JOUR

T1 - Efficient dynamic embeddings of binary trees into hypercubes

AU - Heun, Volker

AU - Mayr, Ernst W.

PY - 2002/4

Y1 - 2002/4

N2 - 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(log2(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 ρ on the hypercube itself in amortized time O(ρ · log2 (L/ρ)) per spawning step, if in each step at most L new leaves are added.

AB - 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(log2(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 ρ on the hypercube itself in amortized time O(ρ · log2 (L/ρ)) per spawning step, if in each step at most L new leaves are added.

KW - Binary tree

KW - Dynamic embedding

KW - Hypercube

KW - Simulation of algorithms

UR - http://www.scopus.com/inward/record.url?scp=0036557586&partnerID=8YFLogxK

U2 - 10.1006/jagm.2002.1218

DO - 10.1006/jagm.2002.1218

M3 - Article

AN - SCOPUS:0036557586

SN - 0196-6774

VL - 43

SP - 51

EP - 84

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -