Minimization of the number of layers for single row routing with fixed street capacity
Teofilo F. Gonzalez, S. Kurki-Gowdara · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1988
A set of three algorithms is presented for solving single-row routine problems with a fixed street capacity using the least number of layers. The main difference among these algorithms is in the strategy used to search for an optimal solution, which greatly affects the performance. At the extreme points of the strategy are algorithms Q and S. The worst-case time complexity is linear for algorithm Q and exponential for algorithm S. The best-case time complexity of all the algorithms is linear. The main disadvantage of algorithm Q is that the constant associated with its time complexity bounds is large. On the other hand, the constant associated with the best-case time complexity bound for algorithm S is small. An experimental evaluation of the performance of the algorithms is presented.>