Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point-Based Algorithm
Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point-Based Algorithm
复制标题
DOI：
10.1109/tcad.2012.2185050
复制
发表时间：
2012-07
影响因子：
2.9
通讯作者：
Chih-Hung Liu;S. Kuo;Der-Tsai Lee;Chun-Syun Lin;Jung-Hung Weng;Shih-Yi Yuan
中科院分区：
文献类型：
--
作者：
Chih-Hung Liu;S. Kuo;Der-Tsai Lee;Chun-Syun Lin;Jung-Hung Weng;Shih-Yi Yuan
针对避障直线Steiner最小树(OARSMT)问题，提出了一种基于Steiner点的算法，该算法在已有的启发式算法中取得了最好的实用性能。我们首先提出了Steiner点位置的新概念，创建了一个具有满意的Steiner点候选的线性空间布线图，以解决大多数现有启发式算法的瓶颈。然后，我们提出了一个基于Steiner点的框架来产生一个解决方案，这是处理OARSMT问题的关键。实验结果表明，该算法同时获得了良好的解质量和速度性能。我们还将基于Steiner点的框架扩展到避障优先方向Steiner树问题，取得了较好的效果。
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.