Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
We consider the problem of routing multiterminal nets in a two-dimensional gate-array. Given a gate-array and a set of nets to be routed, we wish to find a routing that uses as little channel space as possible. We present a deterministic approximation algorithm that uses close to the minimum possible channel space. We cast the routing problem as a new form of zero-one multicommodity flow, an integer-programming problem. We solve this integer program approximately by first solving its linear-program relaxation and then rounding any fractions that appear in the solution to the linear program. The running time of the rounding algorithm is exponential in the number of terminals in a net but polynomial in the number of nets and the size of the array. The algorithm is thus best suited to cases where the number of terminals on each net is small. © 1991 Springer-Verlag New York Inc.
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
M.B. Small, R.M. Potemski
Proceedings of SPIE 1989