One problem in VLSI physical designs is to route multi-terminal nets in the presence of obstacles. This paper presents a polynomial time approximation scheme for construction of a rectilinear minimum tree in the presence of obstacles. Given any m rectanglar obstacles, n nodes andepislon>0, the scheme find a (1+epislon)-approximation to the optimum solution in time of n^(O(1/epsilon)), providing an alternative of previous heuristics.Key words:Rectilinear Steiner Minimum Tree in presence of obstacles, VLSI routing, PTAS, Guillitone cut, approximation algorithm.
Liu, Jian; Zhao, Ying.
A Polynomial Time Approximation Scheme for Rectlinear Steiner Mininum Tree Construction in the Presence of Obstacles.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.