Algorithm for the construction of Rectilinear Steiner Minimum Tree by identifying the clusters of points

Author

Vani, V. ; Prasad, G.R.

Author_Institution

Dept. of Inf. Sci. & Eng., Bangalore Inst. of Technol., Bangalore, India

fYear

2014

fDate

27-28 Feb. 2014

Firstpage

1

Lastpage

4

Abstract

The proposed algorithm constructs Rectilinear Steiner Minimum Tree (RSMT) by applying clustering algorithm to identify the required number of cluster of points and then applies a strategy to construct RSMT for each of the cluster. The clusters are then interconnected to get the final RSMT. The constructed RSMT produces improvement over Rectilinear Minimum Spanning Tree in terms of wire length reduction. RSMT are widely used in the global routing phase of VLSI design and wire length reduction.

Keywords

VLSI; circuit CAD; integrated circuit design; network routing; pattern clustering; trees (mathematics); RSMT; VLSI design; clustering algorithm; global routing phase; point clusters; rectilinear Steiner minimum tree; rectilinear minimum spanning tree; wire length reduction; Algorithm design and analysis; Clustering algorithms; Educational institutions; Joining processes; Routing; Steiner trees; Very large scale integration; Minimum Spanning Tree; Rectilinear Minimum Spanning Tree; Rectilinear Steiner Minimum Tree; VLSI Design;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Communication and Embedded Systems (ICICES), 2014 International Conference on

Conference_Location

Chennai

Print_ISBN

978-1-4799-3835-3

Type

conf

DOI

10.1109/ICICES.2014.7033852

Filename

7033852