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ı: 115

Ö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

    199108

    Sequential and parallel heuristic algorithms for the rectilinear Steiner tree problem

    Doğrulu Steiner ağaç problemi için yaklaşık sonuç veren seri ve paralel algoritmalar

    SERTAÇ CİNEL

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI

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

  3. Tez No

    696264

    Platform and data-aware execution of sparse triangular solve on CPU-GPU heterogeneous systems

    Başlık çevirisi yok

    NAJEEB AHMAD

    Doktora

    İngilizce

    İngilizce

    2021

    Mühendislik BilimleriKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ DİDEM UNAT ERTEN

  4. Tez No

    336855

    Data distribution and performance optimization models for parallel data mining

    Koşut veri madenciliği için veri dağıtımı ve başarım optimizasyon modelleri

    ERAY ÖZKURAL

    Doktora

    İngilizce

    İngilizce

    2013

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

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

Geri Dön