An optimal emulator and VLSI layout for complete binary trees
How complex does a graph need to be in order to emulate an arbitrary size complete binary tree with the same level of efficiency as would be obtained by a directed complete graph? In this paper, this question is answered by showing that any \(N= 2^n\)-node graph needs to have at least \({{3N-2} \over 2}\) edges in order to perform this emulation. Subsequently, a graph is presented which meets this bound, and it is shown how to optimally embed an arbitrary size complete binary tree in the proposed graph. It is also shown how to optimally embed a \(kN\) node cycle in the proposed graph of \(N\) nodes with unit dilation, unit congestion and uniform load of \(k\). Finally optimal VLSI layouts are presented for the proposed graph which require asymptotically same area as the corresponding layouts for complete binary trees.
- On the maximum edge length in VLSI layouts of complete binary trees
- Embedding ternary trees in VLSI arrays
- Expansion of layouts of complete binary trees into grids
- VLSI layouts of complete graphs and star graphs
- scientific article; zbMATH DE number 3864518 (Why is no real title available?)
- Efficient Embeddings of Binary Trees in VLSI Arrays
This page was built for publication: An optimal emulator and VLSI layout for complete binary trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920223)
