A new class of iterative Steiner tree heuristics with good performance
- 1 July 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 11 (7) , 893-902
- https://doi.org/10.1109/43.144853
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 successfulKeywords
This publication has 19 references indexed in Scilit:
- Rectilinear Steiner tree construction by local and global refinementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New algorithms for the rectilinear Steiner tree problemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- Fast heuristic algorithms for rectilinear steiner treesAlgorithmica, 1989
- VLSI Placement and Global Routing Using Simulated AnnealingPublished by Springer Nature ,1988
- The 1-steiner tree problemJournal of Algorithms, 1987
- Computational GeometryPublished by Springer Nature ,1985
- STEINER TREES, STEINER CIRCUITS AND THE INTERFERENCE PROBLEM IN BUILDING DESIGNEngineering Optimization, 1979
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966