A new heuristic for rectilinear Steiner trees

Author

Condamoor, Ravi ; Tollis, Ioannis G.

Author_Institution

Dept. of Comput. Sci., Texas Univ., Dallas, Richardson, TX, USA

fYear

1990

fDate

1-3 May 1990

Firstpage

1676

Abstract

A heuristic algorithm for finding RSTs (rectilinear Steiner trees) is presented. The algorithm was run on a large number of randomly generated data sets. However, the algorithm performed exceptionally well for several data sets, namely, it found steiner trees whose total length was 15 to 18% less than the total length of the corresponding RMSTs (rectilinear minimum spanning trees). The time complexity of the heuristic is O(N log N). The heuristic algorithm is described, and an example is presented. The time complexity of the heuristic and its performance in comparison with well-established techniques are analyzed. The authors also present a graph comparing the lengths of minimum spanning trees to that of the Steiner trees obtained by the heuristic for different values of N. Some possible improvements and variations of the algorithm are suggested

Keywords

VLSI; circuit layout CAD; heuristic programming; printed circuit design; trees (mathematics); C language; RMST; RST; automated VLSI chip layout; convex computer; heuristic algorithm; printed circuit board layout; rectilinear Steiner trees; rectilinear minimum spanning trees; time complexity; Algorithm design and analysis; Computer science; Heuristic algorithms; Integrated circuit interconnections; Joining processes; Printed circuits; Tree graphs; Very large scale integration; Wires; Wiring;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1990., IEEE International Symposium on

Conference_Location

New Orleans, LA

Type

conf

DOI

10.1109/ISCAS.1990.111926

Filename

111926