DocumentCode
3000608
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
Volume
6
fYear
1999
fDate
36342
Firstpage
117
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ISCAS.1999.780109
Filename
780109
Link To Document