About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
Paper
An Algorithm for Exact Rectilinear Steiner Trees for Switchbox with Obstacles
Abstract
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<inf>1</inf>(k)n + F<inf>2</inf>(k)) time, where k is the number of obstacles inside the switchbox and F<inf>1</inf> and F<inf>2</inf> 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