A new class of iterative Steiner tree heuristics with good performance

Author

Kahng, Andrew B. ; Robins, Gabriel

Author_Institution

Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA

Volume

11

Issue

7

fYear

1992

fDate

7/1/1992 12:00:00 AM

Firstpage

893

Lastpage

902

Abstract

A fast approach to the minimum rectilinear Steiner tree (MRST) problem is presented. The method yields results that reduce wire length by up to 2% to 3% over the previous methods, and is the first heuristic which has been shown to have a performance ratio less than 3/2; in fact, the performance ratio is less than or equal to 4/3 on the entire class of instances where the ratio c(MST)/c(MRST) is exactly equal to 3/2. The algorithm has practical asymptotic complexity owing to an elegant implementation which uses methods from computation geometry and which parallelizes readily. A randomized variation of the algorithm, along with a batched variant, has also proved successful

Keywords

VLSI; circuit layout CAD; graph theory; IC layout; asymptotic complexity; batched variant; computation geometry; implementation; iterative Steiner tree heuristics; minimum rectilinear Steiner tree; parallelizes readily; performance ratio; randomized variation; Associate members; Circuits; Costs; Geometry; Helium; Routing; Topology; Very large scale integration; Wire; Wiring;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.144853

Filename

144853