Publication Details
Title: Efficient Dynamic Embeddings of Binary Trees into Hypercubes
Author: V. Heun and E. W. Mayr
Group: ICSI Technical Reports
Date: August 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-023.pdf
Overview:
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. Keywords: Simulation of Algorithms, Hypercubes, Binary Trees, Dynamic Graph Embeddings
Bibliographic Information:
ICSI Technical Report TR-98-023
Bibliographic Reference:
V. Heun and E. W. Mayr. Efficient Dynamic Embeddings of Binary Trees into Hypercubes. ICSI Technical Report TR-98-023, August 1998
Author: V. Heun and E. W. Mayr
Group: ICSI Technical Reports
Date: August 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-023.pdf
Overview:
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. Keywords: Simulation of Algorithms, Hypercubes, Binary Trees, Dynamic Graph Embeddings
Bibliographic Information:
ICSI Technical Report TR-98-023
Bibliographic Reference:
V. Heun and E. W. Mayr. Efficient Dynamic Embeddings of Binary Trees into Hypercubes. ICSI Technical Report TR-98-023, August 1998