J. Nievergelt, J. Pradels, et al.
Information Processing Letters
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
J. Nievergelt, J. Pradels, et al.
Information Processing Letters
J. Cong, A. Kahng, et al.
ISCAS 1992
D.S. Hirschberg, C.K. Wong
Journal of the ACM
David M. Choy, C.K. Wong
BIT