AN O(N LOG N) HEURISTIC FOR STEINER MINIMAL TREE PROBLEMS ON THE EUCLIDEAN METRIC

被引:53
作者
SMITH, JM
LEE, DT
LIEBMAN, JS
机构
[1] NORTHWESTERN UNIV,DEPT ELECT ENGN & COMP SCI,EVANSTON,IL 60201
[2] UNIV ILLINOIS,DEPT MECH & IND ENGN,OPERAT RES LAB,URBANA,IL 61801
关键词
D O I
10.1002/net.3230110104
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
引用
收藏
页码:23 / 39
页数:17
相关论文
共 25 条
[1]  
Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st
[2]   GENERATION OF MINIMAL TREES WITH A STEINER TOPOLOGY [J].
CHANG, SK .
JOURNAL OF THE ACM, 1972, 19 (04) :699-&
[3]  
Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051
[4]   LOWER BOUND FOR STEINER TREE PROBLEM [J].
CHUNG, FRK ;
HWANG, FK .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (01) :27-36
[5]  
COURANT DR, 1941, WHAT IS MATH
[6]  
DRYSDALE RL, 1978, 16TH P ANN ALL C COM, P833
[7]   COMPLEXITY OF COMPUTING STEINER MINIMAL TREES [J].
GAREY, MR ;
GRAHAM, RL ;
JOHNSON, DS .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :835-859
[8]   STEINER MINIMAL TREES [J].
GILBERT, EN ;
POLLAK, HO .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1968, 16 (01) :1-&
[9]  
GRAHAM RL, 1976, B I MATH ACAD SINICA, V4, P177
[10]   O(N LOG N) ALGORITHM FOR SUBOPTIMAL RECTILINEAR STEINER TREES [J].
HWANG, FK .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1979, 26 (01) :75-77