COMPLEXITY OF COMPUTING STEINER MINIMAL TREES

被引：324

作者：

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 [J].

GAREY, MR ;

JOHNSON, DS .

[6] STEINER MINIMAL TREES [J].

GILBERT, EN ;

POLLAK, HO .

[7]

GILBERT EN, 1967, BELL SYST TECH J, V9, P2209

[8]

GRAHAM RL, 1967, RESULTS STEINER MINI

[9] ON STEINERS PROBLEM WITH RECTILINEAR DISTANCE [J].

HANAN, M .

[10]

HANAN M, 1972, DESIGN AUTOMATION DI, V1, P213