COMPLEXITY OF COMPUTING STEINER MINIMAL TREES

被引：319

作者：

GAREY, MR ^{[1
]}

GRAHAM, RL ^{[1
]}

JOHNSON, DS ^{[1
]}

机构：

[1] BELL TEL LABS INC,MURRAY HILL,NJ 07974

来源：

关键词：

D O I：

10.1137/0132072

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

引用

页码：835 / 859

页数：25

共 17 条

[1] AHO AV, TO BE PUBLISHED
[2] AHO AV, 1974, DESIGN ANAL COMPUTER, pCH10
[3] BOYCE WM, 1973, STEINER 72 IMPROVED
[4] BOYCE WM, 1975, IMPROVED PROGRAM FUL
[5] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE
GAREY, MR
JOHNSON, DS
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) : 826 - 834
[6] STEINER MINIMAL TREES
GILBERT, EN
POLLAK, HO
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1968, 16 (01) : 1 - &
[7] GILBERT EN, 1967, BELL SYST TECH J, V9, P2209
[8] GRAHAM RL, 1967, RESULTS STEINER MINI
[9] ON STEINERS PROBLEM WITH RECTILINEAR DISTANCE
HANAN, M
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1966, 14 (02) : 255 - &
[10] HANAN M, 1972, DESIGN AUTOMATION DI, V1, P213