Optimal Routing of Critical But Typical Nets

Routing folklore tells us that a typical net has somewhere between two and four terminals. We present algorithms TRlF'LE and HOMER that compute an optimal rectilinear Steiner minimal tree for nets with three or four terminals respectively. Unlike traditional rectilinear Steiner minimal tree algorithms, TRIPLE and HOMER account for the presence of logic elements and pre-placed wire segments. The algorithms exploit a theorem that we prove that limits the number of potential routing segments that are examined while constructing an optimal solution. The potential routing segments are derived from a generalization of Hightower's line search escape segments.
Note: Abstract extracted from PDF file via OCR

Lavinus, J, and J Cohoon. "Optimal Routing of Critical But Typical Nets." University of Virginia Dept. of Computer Science Tech Report (1992).