Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Cost-Radius Balanced Spanning/Steiner Trees
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E80-A No.4 pp.689-694
Publication Date: 1997/04/20
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Full Text: PDF(419.4KB)
The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.