Liu, JianZhao, Ying2020-09-022020-09-022002-04-18https://hdl.handle.net/11299/215519One 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.en-USReport