The switchbox routing problem (SRP) in which terminals have some flexibility in placement on the border is considered. The general problem with position constraints is NP-complete, as is the problem with only order constraints or separation constraints. The problem is solved for the case in which terminals are permutable within prespecified groups of adjacent vertices, called clusters. Whenever possible, the algorithm determines a terminal assignment such that the resulting SRP is solvable; the total time to assign the terminals and to construct a layout is O(N log N), where N is the number of nets. The results extend to multiple layers and to convex grids.
展开▼
