Sequential and parallel algorithms for the rectilinear steiner tree problem


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2004

Tezin Dili: İngilizce

Öğrenci: NAHİT EMANET

Danışman: CAN ÖZTURAN

Özet:

ÖZET DOĞRULU STEINER AĞAÇ PROBLEMİ İÇİN SERİ VE PARALEL ALGORİTMALAR Doğrulu Steiner ağaç problemi çok büyük ölçekli entegre devre tasarımı (VLSI) ve ağ yapılarında pek çok önemli uygulaması olan NP-complete bir problemdir. Bu tez çalışması doğrulu Steiner ağaç problemini inceler ve bu problemi çözmek için hem seri hem de paralel dallan ve kes algoritmaları önerir. Bu tezde, problemi kısa zamanda çözmemizi sağlayan cutsec ve birbiriyle çakışan güçlü kısıtlamalar adında iki yeni doğrusal programlama kısıtlaması gösterdik. Ayrıca, bir heterojen hesaplama ortamı içinde büyük problem örneklerinin çözümü için paralel mesaj geçişi algoritması sunduk. Hem paralel hem de seri algoritmalar nesne tabanlı yöntembilim kullanılarak C++ programlama diliyle yazılmış bir program içinde bütünleştirilmiştir. Sunulan algoritmaların deneysel sonuçlarına SteinLib kütüphanesi içinden alınmış TSP ve ES1000FST örnekleri üzerinde testler yaparak baktık. Sunulan algoritmaların doğrulu en küçük Steiner ağaç (RSMT) probleminin kesin sonucunu elde etmeleri için gerekli ortalama çalışma zamanının diğer rakip algoritmalardan daha iyi olduğunu gördük. Hazırladığımız programın, değişiklikleri ve geliştirmeleri kolaylaştıran arabirimi sayesinde geliştirilebilecek diğer algoritmalar için bir taban oluşturduğunu söyleyebiliriz.