Generalized terminal connectivity problem for multilayer layout scheme

Given a set of n horizontal (or vertical) wire segments run on different layers with variable widths (or heights), and a set of m terminals placed on different layers and with arbitrary rectangular shapes, a generalization of the terminal connectivity problem (TCP) is considered. This TCP can be applied to facilitate the VLSI or PCB multi-layer layout. First, it is proved that this TCP is NP-hard by showing that it is equivalent to a minimal steiner tree problem, which has been proved NP-complete. Then an efficient algorithm for the TCP is presented which runs in O(m + (1 + c)nn) time (with some preprocessing work). Experimental results are given to verify the effectiveness of the algorithm.