Cost-Radius Balanced Spanning/Steiner Trees

Hideki MITSUBAYASHI  Atsushi TAKAHASHI  Yoji KAJITANI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E80-A  No.4  pp.689-694
Publication Date: 1997/04/20
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
delay,  spanning tree,  steiner tree,  VLSI layout, 

Full Text: PDF(419.4KB)

Summary: 
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.