Minimal Steiner trees in X architecture with obstacles

被引：0

作者：

Luo, CC ^{[1
]}

Hwang, YS ^{[1
]}

Jan, GE ^{[1
]}

机构：

[1] Natl Taiwan Ocean Univ, Dept Comp Sci, Chilung 202, Taiwan

来源：

CDES '05: PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON COMPUTER DESIGN | 2005年

关键词：

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Steiner minimal tree problem in X architecture is the problem of connecting a set terminals Z using orthogonal, diagonal, and vertical edges with minimum length. This problem has many applications, especially for the routing of VLSI circuits. This paper proposes an obstacle-avoiding heuristic for this problem based on the Areibi's concepts and Prim's minimal spanning tree algorithm, and the Steiner ratio of this approach is 1.25. The space and time complexities are O(N-2) and O(N-2 + p(3)N) respectively, where N and p are the numbers of free and terminal vertices (p <= N).

引用

页码：198 / 203

页数：6

共 15 条

[1]

[Anonymous], 1961, CAN MATH BULLETIN, DOI DOI 10.4153/CMB-1961-016-2

[2]

[Anonymous], 1972, COMPLEXITY COMPUTER

[3]

Areibi S, 2001, CANADIAN CONFERENCE ON ELECTRICAL AND COMPUTER ENGINEERING 2001, VOLS I AND II, CONFERENCE PROCEEDINGS, P1067, DOI 10.1109/CCECE.2001.933590

[4]

BOYCE WM, 1977, ACM T MATH SOFTWARE, P194

[5]

Cieslik D., 2001, COMB OPT (SER), V10

[6]

COCKAYNE EJ, 1972, COMBINATORICA, P52

[7]

COULSTON CS, 2003, P ACM GREAT LAK S VL, P1

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

HANAN, M .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1966, 14 (02) :255-&

[9] O(N LOG N) ALGORITHM FOR SUBOPTIMAL RECTILINEAR STEINER TREES [J].

HWANG, FK .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1979, 26 (01) :75-77

[10]

JAN GE, 1997, J MARINE SCI TECHNOL, V5, P95

← 1 2 →