CLOSING THE GAP - NEAR-OPTIMAL STEINER TREES IN POLYNOMIAL-TIME

被引:45
作者
GRIFFITH, J
ROBINS, G
SALOWE, JS
ZHANG, TT
机构
[1] UNIV VIRGINIA,DEPT COMP SCI,CHARLOTTESVILLE,VA 22903
[2] QUESTECH INC,FALLS CHURCH,VA 22043
基金
美国国家科学基金会;
关键词
D O I
10.1109/43.329264
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing MRST heuristic to date is the Iterated 1-Steiner (I1S) method recently proposed by Kahng and Robins. In this paper, we develop a straightforward, efficient implementation of I1S, achieving a speedup factor of three orders of magnitude over previous implementations. We also give a parallel implementation that achieves near-linear speedup on multiple processors. Several performance-improving enhancements enable us to obtain Steiner trees with average cost within 0.25% of optimal, and our methods produce optimal solutions in up to 90% of the cases for typical nets. We generalize IIS and its variants to three dimensions, as well as to the case where all the pins lie on k parallel planes, which arises in, e.g., multilayer routing. Motivated by the goal of reducing the running times of our algorithms, we prove that any pointset in the Manhattan plane has a minimum spanning tree (MST) with maximum degree 4, and that in three-dimensional Manhattan space every pointset has an MST with maximum degree of 14 (the best previous upper bounds on the maximum MST degree in two and three dimensions are 6 and 26, respectively); these results are of independent theoretical interest and also settle an open problem in complexity theory.
引用
收藏
页码:1351 / 1365
页数:15
相关论文
共 47 条
[1]  
Braun D., 1986, 23rd ACM/IEEE Design Automation Conference. Proceedings 1986 (Cat. No.86CH2288-9), P495, DOI 10.1145/318013.318092
[2]   DATA-STRUCTURES FOR ONLINE UPDATING OF MINIMUM SPANNING-TREES, WITH APPLICATIONS [J].
FREDERICKSON, GN .
SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :781-798
[3]   RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].
GAREY, MR ;
JOHNSON, DS .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834
[4]   THE 1-STEINER TREE PROBLEM [J].
GEORGAKOPOULOS, G ;
PAPADIMITRIOU, CH .
JOURNAL OF ALGORITHMS, 1987, 8 (01) :122-130
[5]   STEINER MINIMAL TREES [J].
GILBERT, EN ;
POLLAK, HO .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1968, 16 (01) :1-&
[6]  
GRAHAM RL, 1976, B I MATH ACAD SINICA, V4, P177
[7]   ON STEINERS PROBLEM WITH RECTILINEAR DISTANCE [J].
HANAN, M .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1966, 14 (02) :255-&
[8]   NEW ALGORITHMS FOR THE RECTILINEAR STEINER TREE PROBLEM [J].
HO, JM ;
VIJAYAN, G ;
WONG, CK .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1990, 9 (02) :185-193
[9]  
Hwang F. K., 1992, ANN DISCRETE MATH
[10]   STEINER MINIMAL TREES WITH RECTILINEAR DISTANCE [J].
HWANG, FK .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1976, 30 (01) :104-115