Switchbox Steiner tree problem in presence of obstacles

Author

Miriyala, S. ; Hashmi, J. ; Sherwani, N.

Author_Institution

Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA

fYear

1991

fDate

11-14 Nov. 1991

Firstpage

536

Lastpage

539

Abstract

The authors consider a problem related to global routing of multiterminal nets in VLSI layout. They investigate the problem of finding the minimum Steiner tree in the presence of obstacles when the terminals lie on the boundary of a rectangle (RSTO) and present two results. The first contribution is an exact solution for finding the rectilinear Steiner tree in the presence of an obstacle when the terminals lie on the boundary of a rectangle. Second, an approximation algorithm for RSTO in the presence of k obstacles is given. It is shown that the algorithm has a tight performance bound. A heuristic algorithm which produces solutions very close to the optimal is given.<>

Keywords

VLSI; circuit layout CAD; data structures; heuristic programming; trees (mathematics); RSTO; VLSI layout; approximation algorithm; global routing; heuristic algorithm; minimum Steiner tree; multiterminal nets; obstacles; Approximation algorithms; Computer science; Costs; Heuristic algorithms; Integrated circuit interconnections; Knee; Marine vehicles; Polynomials; Routing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on

Conference_Location

Santa Clara, CA, USA

Print_ISBN

0-8186-2157-5

Type

conf

DOI

10.1109/ICCAD.1991.185325

Filename

185325