Name
Abstract | ||
|---|---|---|
In this paper we present efficient graph embeddings for complete k-ary trees into boolean hypercubes. In particular, we describe an efficient embedding of a complete ternary tree (k = 3) of height h into a hypercube, which achieves dilation 3 and expansion Θ(1.0104...h). The previously best-known result is dilation 2 and expansion Θ(1.333...h). Our embedding achieves exponentially better expansion at the cost of an increase of 1 in the dilation. We also describe efficient embeddings of k-ary trees into hypercubes when k = 2p * 3q for some p, q 0 such that the embeddings achieve small constant dilation. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0743-7315(03)00037-6 | J. Parallel Distrib. Comput. |
Keywords | DocType | Volume |
complete ternary tree,algorithm porting,emulation,trees,k-ary tree,efficient graph embeddings,efficient embeddings,expansion,boolean hypercubes,hypercubes,better expansion,efficient embedding,embeddings,small constant dilation,complete k-ary tree,best-known result,interconnection networks,dilation,graph embedding | Journal | 63 |
Issue | ISSN | Citations |
6 | Journal of Parallel and Distributed Computing | 11 |
PageRank | References | Authors |
0.61 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajay K. Gupta | 1 | 166 | 24.40 |
| Donald Nelson | 2 | 32 | 2.85 |
| Hong Wang | 3 | 398 | 138.00 |