A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem
A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem
复制标题
DOI：
10.1109/tcad.2008.2006085
复制
发表时间：
2008-11
影响因子：
2.9
通讯作者：
Sertac Cinel;C. F. Bazlamaçci
中科院分区：
文献类型：
--
作者：
Sertac Cinel;C. F. Bazlamaçci
直线施泰纳最小树 (RSMT) 问题找到一个最小长度树，该树仅通过水平和垂直线段并在必要时使用额外的点来互连给定的一组点。在本文中，为了加速RSMT的构建，使用了两种最近开发的成功的启发式算法，即Zhou的直线斯坦纳树（RST）和Kahng的批量贪婪算法（BGA）作为基础。在对 RST 进行轻微修改后，产生了非递归且速度相当快的版本，提出了该修改算法的部分并行和分布式形式。使用大型随机数据集的计算测试显示了对 RST 进行修改的优势，并且在工作站集群上进行的测试证明所提出的分布式方法非常有前途，特别是对于大型问题实例。
Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and batched greedy algorithm (BGA) by Kahng , have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a considerably faster version, a partially parallelized and distributed form of this modified algorithm is proposed. Computational tests using large random data sets have shown the advantage of the modification on RST, and tests conducted on a cluster of workstations have proven the proposed distributed approach to be very promising particularly for large problem instances.