Name
Abstract | ||
|---|---|---|
In this paper we introduce a class of trees, called generalized compressed trees. Generalized compressed trees can be derived from complete binary trees by performing certain 'contraction' operations. A generalized compressed tree CT of height h has approximately 25% fewer nodes than a complete binary tree T of height h. We show that these trees have smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLSI layouts than the complete binary trees. We also show that algorithms initially designed for T can be simulated by CT with at most a constant slow-down. In particular, algorithms having non-pipelined computation structure and originally designed for T can be simulated by CT with no slow-down. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1142/S0129053395000142 | INTERNATIONAL JOURNAL OF HIGH SPEED COMPUTING |
Keywords | Field | DocType |
BINARY TREE MACHINE, EMBEDDING, HYPERCUBE, PARALLEL ALGORITHM, PIPELINED COMPUTATION, NODE LOAD, SIMULATION, VLSI LAYOUT (2-DIMENSIONAL AND 3-DIMENSIONAL) | Discrete mathematics,Tree traversal,Metric tree,Binary tree,Optimal binary search tree,Weight-balanced tree,Random binary tree,Ternary search tree,Mathematics,Binary search tree | Journal |
Volume | Issue | ISSN |
7 | 2 | 0129-0533 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajay K. Gupta | 1 | 166 | 24.40 |
| Hong Wang | 2 | 398 | 138.00 |