DocumentCode
2598986
Title
An exact rectilinear Steiner tree algorithm
Author
Salowe, J.S. ; Warme, D.M.
Author_Institution
Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA
fYear
1993
fDate
3-6 Oct 1993
Firstpage
472
Lastpage
475
Abstract
Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for an input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 minutes. Previous algorithms could only solve 16 or 17-point problems within the 30-minute time bound
Keywords
circuit layout; circuit layout CAD; computational complexity; mathematics computing; minimisation of switching nets; trees (mathematics); exact rectilinear Steiner tree algorithm; horizontal minimum tree; input terminals; minimal tree; shortest interconnection; vertical edges; workstation; Algorithm design and analysis; Computer science; Ear; Length measurement; Polynomials; Routing; Steiner trees; Topology; Very large scale integration; Workstations;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Design: VLSI in Computers and Processors, 1993. ICCD '93. Proceedings., 1993 IEEE International Conference on
Conference_Location
Cambridge, MA
Print_ISBN
0-8186-4230-0
Type
conf
DOI
10.1109/ICCD.1993.393331
Filename
393331
Link To Document