Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR01-069 | 6th March 2002 00:00

Optimizing the Layout of a Complete Tree


Revision #1
Authors: Robert Albin Legenstein
Accepted on: 6th March 2002 00:00
Downloads: 3274


Tree-like organizations are a fundamental parallel processing
structure. The layout of trees has so far been studied mostly for
trees of degree four or less. In this article, we give tight upper
and lower bounds on the total wire length of complete m-ary trees
(m>=2) on a two-dimensional grid if the leaves are constraint to
lie on a grid line. For the case of m=2 we reproof an older result
of Fischer and Paterson in a more direct way. The construction results
in a significant reduction of the total wire length compared to
the obvious ``symmetric'' layout.


TR01-069 | 24th October 2001 00:00

Optimizing the Layout of a Balanced Tree

Authors: Robert Albin Legenstein
Publication: 24th October 2001 11:25
Downloads: 3988


It is shown that the total wire length of layouts of a
balanced binary tree on a 2-dimensional grid can be reduced by 33%
if one does not choose the obvious ``symmetric'' layout strategy.
Furthermore it is shown that the more efficient layout strategy that
is presented in this article is optimal, not only for binary trees
but for m-ary trees with any m >= 2.

ISSN 1433-8092 | Imprint