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

共 50 条

[21] Improved computation of plane Steiner Minimal Trees
Cockayne, E.J.
Hewgill, D.E.
Algorithmica (New York), 1992, 7 (2-3): : 219 - 229
[22] Absorbing Angles, Steiner Minimal Trees, and Antipodality
H. Martini
K. J. Swanepoel
P. Oloff de Wet
Journal of Optimization Theory and Applications, 2009, 143 : 149 - 157
[23] ON FINDING RECTILINEAR STEINER MINIMAL-TREES
BASART, JM
RIFA, J
REVISTA DE INFORMATICA Y AUTOMATICA, 1989, 22 (02): : 40 - 45
[24] Steiner Minimal Trees in rectilinear and octilinear planes
Shang, Song Pu
Jing, Tong
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (09) : 1577 - 1586
[25] Steiner minimal trees in Lp2
Discrete Math, 1-3 (39):
[26] STEINER MINIMAL TREES FOR ZIGZAG LINES WITH LADDERS
He Yong Yang QifanDept.ofMath.
Applied Mathematics:A Journal of Chinese Universities, 2001, (02) : 178 - 184
[27] Steiner minimal trees for zigzag lines with ladders
He Y.
Yang Q.
Applied Mathematics-A Journal of Chinese Universities, 2001, 16 (2) : 178 - 184
[28] Absorbing Angles, Steiner Minimal Trees, and Antipodality
Martini, H.
Swanepoel, K. J.
de Wet, P. Oloff
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2009, 143 (01) : 149 - 157
[29] STEINER MINIMAL-TREES FOR REGULAR POLYGONS
DU, DZ
HWANG, FK
WENG, JF
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (01) : 65 - 84
[30] Full minimal Steiner trees on lattice sets
Brazil, M
Rubinstein, JH
Thomas, DA
Weng, JF
Wormald, NC
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 78 (01) : 51 - 91

← 1 2 3 4 5 →