The authors consider a problem related to global routing of multiterminal nets in VLSI layout. They investigate the problem of finding the minimum Steiner tree in the presence of obstacles when the terminals lie on the boundary of a rectangle (RSTO) and present two results. The first contribution is an exact solution for finding the rectilinear Steiner tree in the presence of an obstacle when the terminals lie on the boundary of a rectangle. Second, an approximation algorithm for RSTO in the presence of k obstacles is given. It is shown that the algorithm has a tight performance bound. A heuristic algorithm which produces solutions very close to the optimal is given.
展开▼
