Title :
A linear time algorithm for computing hexagonal Steiner minimum trees for terminals on the boundary of a regular hexagon
Author :
Lin, Guo-Hui ; Xue, Guoliang
Author_Institution :
Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA
Abstract :
In this paper, we present a linear time algorithm for computing the hexagonal Steiner minimum tree for a set of points on the boundary of a regular hexagon. Computational results on randomly generated test problems show that our algorithm can find the optimal solutions on a 200 MHz Pentium within 18 seconds for n as large as 20000. It is expected that techniques of this paper may be generalized to the case where the points are on the boundary of a polygon
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; network topology; trees (mathematics); VLSI physical design; boundary terminals; hexagonal Steiner minimum trees; linear time algorithm; optimal solutions; regular hexagon; Algorithm design and analysis; Communication networks; Computer science; Joining processes; Routing; Steiner trees; Surface-mount technology; Testing; Very large scale integration; Wires;
Conference_Titel :
Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on
Conference_Location :
Geneva
Print_ISBN :
0-7803-5482-6
DOI :
10.1109/ISCAS.2000.857061
