O(N LOG N) ALGORITHM FOR SUBOPTIMAL RECTILINEAR STEINER TREES

被引：36

作者：

HWANG, FK

机构：

[1] Bell Laboratories, Murray Hill

来源：

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS | 1979年 / 26卷 / 01期

关键词：

D O I：

10.1109/TCS.1979.1084551

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

引用

页码：75 / 77

页数：3

共 12 条

[1]

AHO AV, 1974, DESIGN ANAL COMPUTER, P470

[2] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

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

HANAN, M .

[4]

HANAN M, 1965, RC1375 IBM RES REP

[5] STEINER MINIMAL TREES WITH RECTILINEAR DISTANCE [J].

HWANG, FK .

[6]

HWANG FK, UNPUBLISHED

[7]

Kruskal J.B., 1956, P AM MATH SOC, V7, P3, DOI [10.2307/2033241, DOI 10.1090/S0002-9939-1956-0078686-7, 10.1090/S0002-9939-1956-0078686-7]

LEE, JH ;

BOSE, NK ;

HWANG, FK .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1976, 23 (07) :470-476

[9] SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS [J].

PRIM, RC .

BELL SYSTEM TECHNICAL JOURNAL, 1957, 36 (06) :1389-1401

[10]

Shamos M. I., 1975, 16TH P IEEE S F COMP, P151, DOI DOI 10.1109/SFCS.1975.8