Optimal Dynamic Embeddings of Complete Binary Trees Into Hypercubes
| Title | Optimal Dynamic Embeddings of Complete Binary Trees Into Hypercubes |
| Publication Type | Technical Report |
| Year of Publication | 1998 |
| Authors | Heun, V., & Mayr E. W. |
| Other Numbers | 1142 |
| Keywords | Complete Binary Trees, Graph Embeddings, Hypercubes, Simulation of Algorithms |
| Abstract | The double-rooted complete binary tree is a complete binary tree where the root is replaced by an edge. It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into the hypercube does not provide any hint how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings of large binary trees with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Since complete binary trees are similar to double-rooted complete binary trees, our results can be immediately transfered to complete binary trees. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1998/tr-98-022.pdf |
| Bibliographic Notes | ICSI Technical Report TR-98-022 |
| Abbreviated Authors | V. Heun and E. W. Mayr |
| ICSI Publication Type | Technical Report |