Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection

摘要

For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, this paper presents a Steiner-point based algorithm to achieve the best practical performance in wirelength and run time. Unlike many previous works, the Steiner-based framework is more focused on the usage of Steiner points instead of the handling of obstacles. This paper also proposes a new concept of Steiner point locations to provide an effective as well as efficient way to generate desirable Steiner point candidates. Experimental results show that this algorithm achieves the best solution quality in Θ(n log n) empirical time, which was originally generated by applying the maze routing on an Ω(n²)-space graph. The Steiner-point based framework and the new concept of Steiner point locations can be applied to future research on the OARSMT problem and its generations, such as the multi-layer OARSMT problem. Categories and Subject Descriptors: B.7.2 [Integrated Circuits]: Design Aids General Terms: Algorithms, Performance, Design