Item Details

Print View

Optimal Rectilinear Steiner Tree Routing in the Presence of Obstacles (Supercedes CS-92-39, CS-93-15, and CS-93-19)

Ganley, J; Cohoon, J
Format
Report
Author
Ganley, J
Cohoon, J
Abstract
This paper presents a new model for VLSI routing in the presence of obstacles, that transforms any routing instance from a geometric problem into a graph problem. It is the first model that allows computation of optimal obstacle-avoiding rectilinear Steiner trees in time corresponding to the instance size (the number of terminals and obstacle border segments) rather than the size of the routing area. For the most common multi-terminal critical nets---those with three or four terminals---we observe that optimal trees can be computed as efficiently as good heuristic trees, and present algorithms that do so. For nets with five or more terminals, we present algorithms that heuristically compute obstacle-avoiding Steiner trees. Analysis and experimental results demonstrate that the model and algorithms work well in both theory and practice. Also presented are several theoretical results: a derivation of the Steiner ratio for obstacle-avoiding rectilinear Steiner trees, and complexity results for two special cases of the problem.
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1994
Published Date
1994
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online