Degree Type
Thesis
Date of Award
2010
Degree Name
Master of Science
Department
Electrical and Computer Engineering
First Advisor
Chris Chu
Abstract
Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction
is becoming one of the most sought after problems in modern design
flow. In this thesis we present an algorithm to route a
multi-terminal net in the presence of obstacles. Ours is a top down
approach which includes partitioning the initial solution into
subproblems and using obstacle aware version of Fast Lookup Table based Wirelength Estimation (OA-FLUTE) at a lower level to generate an OAST followed by recombining them with some backend refinement. To construct an initial connectivity graph we use a novel obstacle-avoiding
spanning graph (OASG) algorithm which is a generalization of Zhou's
spanning graph algorithm without obstacle presented in ASPDAC 2001. The runtime complexity of our algorithm is O(n log n).
DOI
https://doi.org/10.31274/etd-180810-2776
Copyright Owner
Gaurav Ajwani
Copyright Date
2010
Language
en
Date Available
2012-04-30
File Format
application/pdf
File Size
45 pages
Recommended Citation
Ajwani, Gaurav, "Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction" (2010). Graduate Theses and Dissertations. 11196.
https://lib.dr.iastate.edu/etd/11196
