Item Details

Print View

Optimal Routing of Critical But Typical Nets

Lavinus, J; Cohoon, J
Format
Report
Author
Lavinus, J
Cohoon, J
Abstract
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
Language
English
Date Received
2012-10-30
Published
University of Virginia, Department of Computer Science, 1992
Published Date
1992
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online