Title :
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
fDate :
7/1/1992 12:00:00 AM
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;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on