DocumentCode
1954908
Title
A linear-time Steiner tree routing algorithm for terminals on the boundary of a rectangle
Author
Cohoon, J.P. ; Richards, D.S. ; Salowe, J.S.
Author_Institution
Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA
fYear
1988
fDate
7-10 Nov. 1988
Firstpage
402
Lastpage
405
Abstract
The problem of finding the minimum-length rectilinear Steiner tree that connects a set of points on the boundary of a rectangle is considered. A linear time algorithm for this problem is presented. The algorithm was implemented in C and executed on a Sun3 workstation. Many examples were solved in a fraction of a second. An example with over 250 terminals took 6.5 s.<>
Keywords
circuit layout CAD; computational complexity; network topology; trees (mathematics); 6.5 s; C program; Sun3 workstation; linear time algorithm; minimum-length rectilinear Steiner tree; points connection; rectangle boundary; routing algorithm; terminals; Computer science; Integrated circuit interconnections; Partitioning algorithms; Polynomials; Road transportation; Routing; Steiner trees; Topology; Very large scale integration; Wire;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location
Santa Clara, CA, USA
Print_ISBN
0-8186-0869-2
Type
conf
DOI
10.1109/ICCAD.1988.122537
Filename
122537
Link To Document