Abstract

One of the key problems in VLSI interconnect design is the topology construction of signal nets with the minimum cost. The Steiner tree problem is to find the tree structure which connects all pins of the signal net such that the wire length (i.e., cost) can be minimized. If all edges of the tree are restricted to the horizontal and vertical directions as are the case in VLSI design, the problem is called rectilinear Steiner tree (RST).The problem of optimizing interconnections between microelectronic devices is an evolving area under VLSI architectures. Steiner tree is a fundamental problem in the automatic inter-connects optimization for VLSI design. Existing methodologies using a Steiner tree approach are not optimal in terms of path length.

Keyword

Rectilinear, Steiner, Graph, Topology and VLSI.

Cite this article

Refference

[1][1]Hwang FK. An O (n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM. 1979; 26(2):177-82.

[2][2]Hanan M. On Steiner s problem with rectilinear distance. SIAM Journal on Applied Mathematics. 1966; 14(2):255-65.

[3][3]Mandoiu II, Vazirani VV, Ganley JL. A new heuristic for rectilinear Steiner trees. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2000; 19(10):1129-39.

[4][4]Hwang FK. On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics. 1976; 30(1):104-14.

[5][5]Hwang FK, Richards DS. Steiner tree problems. Networks. 1992; 22(1):55-89.

[6][6]Tang Y, Yang W, Guo T. Definition and algorithms for reliable Steiner tree problem. Journal of Systems Science and Complexity. 2015; 28(4):876-86.

[7][7]Cong J, He L, Koh CK, Madden PH. Performance optimization of VLSI interconnect layout. Integration, the VLSI Journal. 1996; 21(1-2):1-94.

[8][8]Bienkowski M, Kraska A, Schmidt P. A deterministic algorithm for online Steiner tree leasing. In workshop on algorithms and data structures 2017 (pp. 169-80). Springer, Cham.

[9][9]Gologranc T. Graphs with 4-Steiner convex balls. Taiwanese Journal of Mathematics. 2015; 19(5):1325-40.