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
- Tez No: 199108
- Danışmanlar: YRD. DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
- Anahtar Kelimeler: Algoritma Analizi, Çizge Algoritmaları, Dağıtık Algoritmalar, Doğrulu Steiner Ağaç Problemi, Yaklaşık Algoritmalar, Analysis of Algorithms, Approximation Algorithms, DistributedAlgorithms, Graph Theory, Rectilinear Steiner Tree
- Yıl: 2006
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Steiner Ağaç Problemi birçok uygulama alanı bulunan en gözde çizgeproblemlerinden biridir. Bu problemin Hanan tarafından tanımlanan doğrulu biçimi,Çok Büyük Ölçekli Tümleşik (VLSI) Bilgisayar Destekli Tasarım (CAD) işlemininfiziksel tasarım evresinde temel bir soruna çözüm olması nedeniyle özel bir ilgiçekmiştir. Doğrulu Steiner Ağaç Problemi, verilen bir nokta kümesindeki noktaları,fazladan noktalar da kullanabilerek, yalnızca yatay ve dikey doğrularla birleştirenen kısa uzunluktaki ağacı bulmaya çalışır. Problemi kesin sonuç bularak çözençeşitli algoritmalar bulunmaktadır. Ancak problem NP-tamdır ve dolayısıylaözellikle büyük nokta kümeleri için yaklaşık çözüm veren algoritmalarkullanılmalıdır. Bu tez çalışmasında öncelikle yaklaşık çözüm veren algoritmalarüzerinde inceleme yapılmış ve sonrasında yakın zamanda Kahng et. al. tarafındangeliştirilen RST ve Zhou tarafından geliştirilen BGA algoritmaları çalışılmış ve dederinlemesine incelenmiştir. Her iki algoritma da teknik yazında çoğunun kendiarka planları bulunan daha küçük problemlere bölünmüştür. BGA ve RST üzerindeyapılan analiz sonucu tez çalışmasında RST üzerine daha hızlı ve tekrarlamasız birdeğişiklik önerilmiştir. Değiştirilmiş algoritmanın verimliliği hem rasgele hem deVLSI referans örnekleri için test edilmiş ve de gösterilmiştir. Bu algoritmanındağıtık hesaplama ortamı için kısmen paralel biçimi önerilmiştir. Bu algoritma MPI( mesaj gönderim arayüzü ) altyapısı kullanılarak gerçeklenmiş ve de birbirineküme şeklinde bağlı iş istasyonları üzerinde karşılaştırmalı testler yapılmıştır.Önerilen dağıtık algoritmanın özellikle büyük problem örnekleri için umut vericiolduğu gösterilmiştir.
Özet (Çeviri)
The Steiner Tree problem is one of the most popular graph problems and has manyapplication areas. The rectilinear version of this problem, introduced by Hanan, hastaken 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 thatinterconnects a given set of points by only horizontal and vertical line segments,enabling the use of extra points. There are various exact algorithms. However theproblem is NP-complete hence approximation algorithms have to be used especiallyfor large instances. In this thesis work, first a survey on heuristics for the RectilinearSteiner Tree Problem is conducted and then two recently developed successfulalgorithms, BGA by Kahng et. al. and RST by Zhou have been studied andinvestigated deeply. Both algorithms have subproblems, most of which haveindividual backgrounds in literature. After an analysis of BGA and RST, the thesisproposes a modification on RST, which leads to a faster and non-recursive version.The efficiency of the modified algorithm has been validated by computational testsusing both random and VLSI benchmark instances. A partially parallelized versionof the modified algorithm is also proposed for distributed computing environments.It is implemented using MPI (message passing interface) middleware and the resultsof comparative tests conducted on a cluster of workstations are presented. Theproposed distributed algorithm has also proved to be promising especially for largeproblem instances.
Benzer Tezler
- Optıcut: Desen minimizasyonlu tek boyutlu stok kesme problemi için yeni bir sezgisel yaklaşım
Opticut: A new heuristic algorithm for the one-dimensional cutting stock problem with pattern minimisation
NAHSEN KAYHAN
Doktora
Türkçe
2025
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ESRA TEKEZ
- 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
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Küre üzerinde 3 boyutlu gezgin satıcı problemi çözümünde yapay atom algoritması optimizasyonunun paralel programlama ile uygulaması
Application of artificial atom algorithm optimizationto 3-dimensional traveling salesman problem solutionon sphere by parallel programming
AYŞE NUR ALTINTAŞ TANKÜL
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURHAN SELÇUK
- Gezgin satıcı probleminin hadoop üzerinde çalışan paralel genetik algoritma ile çözümü
Parallel genetic algorithm to solve traveling salesman problem on hadoop cluster
HARUN RAŞİT ER
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN
- Protein-protein interaction network alignment using GPU
GPU kullanarak protein – protein etkıileşim ağı hizalama
MOHAMMAD SOHAIB
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKadir Has ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ZEKİ BOZKUŞ