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
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;
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
DOI :
10.1109/ICCD.1993.393331
