ISU Electrical and Computer Engineering Archives

Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction

AJWANI, GAURAV (2010) Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction. Masters thesis, Iowa State University.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.


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 in ASPDAC 2001. The runtime complexity of our algorithm is O(n log n).

EPrint Type:Thesis (Masters)
Uncontrolled Keywords:Physical Design, Routing , Steiner Tree , RSMT ,OARSMT
Subjects:Computer Engineering > VLSI > VLSI CAD
ID Code:537
Identification Number:Identification Number UNSPECIFIED
Deposited By:Gaurav Ajwani
Deposited On:06 February 2010

Archive Staff Only: edit this record