Probability-based approach to rectilinear Steiner tree problems

The rectilinear Steiner tree (RST) problem is of essential importance to the automatic interconnect optimization for VLSI design. In this paper, we present a class of probability-based approaches toward the best solutions under statistical sense and show their performance in comparison with the state-of-the-art algorithm. Experiments conducted on both small- and large-size problems indicate that the proposed approaches lead to promising results in terms of wire length and/or CPU time. The potential advantages with our technique are also discussed for further applications.