Title :
Balancing Steiner minimum trees and shortest-path trees in the rectilinear plane
Author :
Lin, Guo-Hui ; Xue, Guoliang
Author_Institution :
Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA
Abstract :
We consider the problem of balancing shortest-path trees and Steiner minimum trees in the rectilinear plane. This problem has applications in telecommunication, wire routing and VLSI physical design. We present a polynomial time approximation algorithm which simultaneously approximates both the shortest-path tree and the Steiner minimum tree. Previous results guarantee a balanced approximation ratio of about 2.4142. Our algorithm improves the value to 2.0806
Keywords :
VLSI; integrated circuit layout; network routing; telecommunication network routing; trees (mathematics); Steiner minimum trees; VLSI physical design; balanced approximation ratio; polynomial time approximation algorithm; rectilinear plane; shortest-path trees; telecommunication routing; wire routing; Application software; Computer science; Costs; Delay; Polynomials; Routing; Steiner trees; Surface-mount technology; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-5471-0
DOI :
10.1109/ISCAS.1999.780109
