A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem


Cinel S., BAZLAMAÇCI C. F.

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, cilt.27, ss.2083-2087, 2008 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 27 Konu: 11
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1109/tcad.2008.2006085
  • Dergi Adı: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
  • Sayfa Sayıları: ss.2083-2087

Özet

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 hatched greedy algorithm (BGA) by Kahng et al., 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.