Tez No	İndirme	Tez Künye	Durumu
152566	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	Sequential and parallel algorithms for the rectilinear steiner tree problem / Doğrulu steiner ağaç problemi için seri ve paralel algoritmalar Yazar:NAHİT EMANET Danışman: DOÇ.DR. CAN ÖZTURAN Yer Bilgisi: Boğaziçi Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2004 115 s.
Ö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.
IV ABSTRACT SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE RECTILINEAR STEINER TREE PROBLEM The rectilinear Steiner tree problem is an NP-complete problem with many important applications in networks and very large scale integration (VLSI) design. This thesis examines the rectilinear Steiner tree problem and proposes sequential and parallel branch and cut algorithms to solve it. In this thesis, we present two new LP constraints, cutsec constraints and strong incompatibility constraints that allow us to greatly reduce the time to solve the prob lem. We also present a message passing parallel algorithm to solve large problem instances in an heterogenous computing environment. Both sequential and parallel algorithms are unified in a program that is written in C++ programming language by using object oriented methodology. We look at the experimental results of the presented algorithms by performing benchmark tests on TSP and ES1000FST instances from the SteinLib library. Average running time of the algorithms to solve the rectilinear Steiner minimal tree (RSMT) problem to optimality are better than that of other competing algorithms. We can also say that our program can be a base for other new developing algo rithms due to its interface that facilitates improvements and modifications.