Sequential and parallel heuristic algorithms for the rectilinear Steiner tree problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Elektrik ve Elektronik Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2006

Öğrenci: SERTAÇ CİNEL

Danışman: CÜNEYT FEHMİ BAZLAMAÇCI

Özet:

The Steiner Tree problem is one of the most popular graph problems and has many application areas. The rectilinear version of this problem, introduced by Hanan, has taken special attention since it addresses a fundamental matter in “Physical Design” phase of the Very Large Scale Integrated (VLSI) Computer Aided Design (CAD) process. The Rectilinear Steiner Tree Problem asks for a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments, enabling the use of extra points. There are various exact algorithms. However the problem is NP-complete hence approximation algorithms have to be used especially for large instances. In this thesis work, first a survey on heuristics for the Rectilinear Steiner Tree Problem is conducted and then two recently developed successful algorithms, BGA by Kahng et. al. and RST by Zhou have been studied and investigated deeply. Both algorithms have subproblems, most of which have individual backgrounds in literature. After an analysis of BGA and RST, the thesis proposes a modification on RST, which leads to a faster and non-recursive version. The efficiency of the modified algorithm has been validated by computational tests using both random and VLSI benchmark instances. A partially parallelized version of the modified algorithm is also proposed for distributed computing environments. It is implemented using MPI (message passing interface) middleware and the results of comparative tests conducted on a cluster of workstations are presented. The proposed distributed algorithm has also proved to be promising especially for large problem instances.