Jingsheng Cong, Andrew B. Kahng, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
The switchbox rectilinear Steiner tree problem is to construct an optimal rectilinear Steiner tree interconnecting n terminals on the perimeter of a switchbox without crossing any obstacles inside the switchbox. However, intersecting boundaries of obstacles is allowed. We present an algorithm that computes an optimal switchbox rectilinear Steiner tree in O(F(k)n + F(k)) time, where k is the number of obstacles inside the switchbox and F and F are exponential functions of k. For any constant k, the proposed algorithm runs in O(n) time. As an immediate extension, we can generate m Steiner trees in O(mn) time, and among them, select the best one. © 1992 IEEE
Jingsheng Cong, Andrew B. Kahng, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Majid Sarrafzadeh, C.K. Wong
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
A. Albrecht, E. Hein, et al.
Artificial Intelligence in Medicine
D.T. Lee, C.D. Yang, et al.
IEEE TC