A deep-submicron Steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for t he generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as "Deep-submicron Steiner tree", as mini mizing the number of Steiner nodes is crucial for signal integrity issues i n deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The i dea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nod es) tree of small cost. The simulation results show the high efficiency of our approach. (C) 2000 E lsevier Science Ltd. All rights reserved.