P.C. Yue, C.K. Wong
International Journal of Computer & Information Sciences
We study global routing of multiterminal nets. We propose a new global router; each step consists of finding a tree, called a Steiner min-max tree, that is a Steiner tree with maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). We propose an 0( min { e loglog e, n2}) time algorithm for obtaining a Steiner min-max tree in a weighted graph with e edges and n vertices (this result should be contrasted with the W-completeness of the traditional minimum-length Steiner tree problem). Experimental results on difficult examples, on randomly generated data, on master slice chips, and on benchmark examples from the Physical Design Workshop are included. © 1990 IEEE
P.C. Yue, C.K. Wong
International Journal of Computer & Information Sciences
Hongbing Fan, Yu-Liang Wu, et al.
Graphs and Combinatorics
C. Chiang, C.K. Wong, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Jingsheng Cong, Andrew B. Kahng, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems