On the maximum edge length in VLSI layouts of complete binary trees (Q1081305)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the maximum edge length in VLSI layouts of complete binary trees |
scientific article |
Statements
On the maximum edge length in VLSI layouts of complete binary trees (English)
0 references
1986
0 references
A recently suggested layout of complete binary trees is carefully analysed to obtain an exact value for the length of its longest edge. Although the layout achieves the asymptotic lower bound of \(\Omega\) (\(\sqrt{n}/\log n)\), it is shown that as long as the tree has less than \(2^{16}\) leaves, the well-known H-tree layout having a maximum edge length of \(\Theta\) (\(\sqrt{n})\) turns out to be superior. Therefore, the H-tree layout should be preferred for most realistic tree sizes.
0 references