Global Routing Based on Steiner Min-Max Trees

Abstract

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