Search

We consider Steiner minimal trees (SMT's) in metrics defined by given orientations. The problem is motivated by wiring considerations of VLSI chips when the wiring direction is not restricted to only horizontal and vertical. In particular, we concentrate on the case when the given orientations form angles of 0 [degrees], 60 [degrees], and 120 [degrees] ([[Lambda].sub.3]-metric) since many interesting results can be obtained which may shed light on other metrics in the family. Specifically, we show that any SMT can be transformed to one with their Steiner points located on the grid points of a multilevel grid, where the number of levels can be quite small. based on this result, we have developed a simulated annealing-based algorithm to generate near-optimal SMT's. Empirical results and comparisons with Euclidean cases are also given. Index Terms - Multilevel grid, orientation metrics, simulated annealing, Steiner tree problem, very large-scale integration.

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.sub.1](k)n + [F.sub.2](k)) time, where k is the number of obstacles inside the switchbox and [F.sub.1] and [F.sub.2] 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.