Geri Dön

Sequential and parallel algorithms for the rectilinear steiner tree problem

Doğrulu steiner ağaç problemi için seri ve paralel algoritmalar

  1. Tez No: 152566
  2. Yazar: NAHİT EMANET
  3. Danışmanlar: DOÇ.DR. CAN ÖZTURAN
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2004
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Ö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.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    79344

    Algorithms for linear and convex feasibility problems: A Brief study of iterative projection, localization and subgradient methods

    Lineer ve konveks fizibilite problemleri için algoritmalar

    SÜLEYMAN HAKAN ÖZAKTAŞ

    Doktora

    İngilizce

    İngilizce

    1998

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA AKGÜL

  2. Tez No

    58591

    Pararllel rendering algorithms for distributed-memory multicomputers

    Çok işlemcili dağıtık hafızalı bilgisayarlarda paralel görüntüleme algoritmaları

    TAHSİN MERTEFE KURÇ

    Doktora

    İngilizce

    İngilizce

    1997

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  3. Tez No

    65717

    Bir çokluişlemci sisteminde paralel değerlendirme programları

    Başlık çevirisi yok

    MUSTAF MURAT İNCEOĞLU

    Doktora

    Türkçe

    Türkçe

    1997

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. SİNAN YILMAZ

  4. Tez No

    15567

    A Fast fourier transform implementation and performance evaluation on a transputer based parallel computer system

    Transputer temelli bir paralel bilgisayar sisteminde hızlı Fourier dönüşüm uygulaması ve performans hesabı

    CÜNEYT BAZLAMAÇCI

    Yüksek Lisans

    İngilizce

    İngilizce

    1991

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    PROF.DR. HASAN GÜRAN

  5. Tez No

    24469

    Aplication of a prototype parallel processing computer for a recurrent neural network model

    Başlık çevirisi yok

    BEKİR ALPER PAKSOY

    Yüksek Lisans

    İngilizce

    İngilizce

    1992

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Sistem ve Kontrol Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. KEMAL CILIZ

Geri Dön