Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point Based Algorithm
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
31
Journal Issue
7
Pages
1050-1060
Date Issued
2012-01
Author(s)
Abstract
For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance.
SDGs
Type
journal article