Optimal Routing of Critical But Typical Nets

Authors:Lavinus, J, Department of Computer ScienceUniversity of Virginia Cohoon, J, Department of Computer ScienceUniversity of Virginia

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

All rights reserved (no additional license for public reuse)
Source Citation:

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

University of Virginia, Department of Computer Science
Published Date: