On the Construction of Optimal Obstacle-Avoiding Rectilinear Steiner Minimum Trees
On the Construction of Optimal Obstacle-Avoiding Rectilinear Steiner Minimum Trees
复制标题
DOI：
10.1109/tcad.2010.2098930
复制
发表时间：
2011-05
影响因子：
2.9
通讯作者：
Tao Huang;Liang Li;Evangeline F. Y. Young
中科院分区：
文献类型：
--
作者：
Tao Huang;Liang Li;Evangeline F. Y. Young
提出了一种优化求解避障矩形Steiner树(OARSMT)问题的有效方法。我们的工作是基于GeoSteiner方法，在该方法中，首先构造完整的Steiner树(FST)，然后将其组合成矩形Steiner最小树(RSMT)。我们对算法进行了修改和扩展，以允许布线区域中存在障碍物。对于每个路由障碍，我们首先引入位于其四角的四个虚拟终端。然后，我们给出了带有阻塞的FST的定义，并证明了它们将遵循一些非常简单的结构。在这些观测的基础上，提出了一种构建OARSMTs的两阶段方法。在第一阶段，我们生成一组带有阻塞的FST。在第二阶段，使用第一阶段产生的FSTs来构造OARSMT。最后，在几个基准上进行了实验。结果表明，该方法能够处理存在多个障碍物的数百个终端的优化问题，并在合理的时间内产生最优解。
This paper presents an efficient method to solve the obstacle-avoiding rectilinear Steiner tree (OARSMT) problem optimally. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a rectilinear Steiner minimum tree (RSMT). We modify and extend the algorithm to allow obstacles in the routing region. For each routing obstacle, we first introduce four virtual terminals located at its four corners. We then give the definition of FSTs with blockages and prove that they will follow some very simple structures. Based on these observations, a two-phase approach is developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs with blockages. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Finally, experiments on several benchmarks are conducted. Results show that the proposed method is able to handle problems with hundreds of terminals in the presence of multiple obstacles, generating an optimal solution in a reasonable amount of time.