Multilevel graph partitioning: An evolutionary approach
Çok seviyeli çizge parçalama: Evrimsel bir yaklaşım
- Tez No: 93368
- Danışmanlar: Belirtilmemiş.
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Çizge Kuramı, Çizge Parçalama, Çok Seviyeli Çizge Parçalama, Genetik Algoritmalar. iv "EC ÎİKSKÖCEET1M KüSSUi, Genetik algoritmalar, Grafik bölümleme, Graph Theory, Graph Partitioning, Multilevel Graph Partitioning, Genetic Algorithms. iii, Genetic algorithms
- Yıl: 2000
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
oz ÇOK SEVİYELİ ÇİZGE PARÇALAMA: EVRİMSEL BİR YAKLAŞIM Küçükpetek, Süheyda Yüksek Lisans, Bilgisayar Mühendisliği Bölümü, Tez Yöneticisi: Doç. Dr. Faruk Polat Eylül 2000, 76 sayfa Dengeli çizge parçalama problemi yönlendirilmemiş bir çizgenin mümkün olan en az sayıda düğüm ya da kenar çıkanmıyla, dengeli parçalara bölünmesidir. Problemin çözümü, Çok Geniş Ölçekli Tümleşik devre tasarımı, çok işlemcili sistemlerde yük dengelemesi, iç içe bölme algoritması ve iş planlaması gibi birçok problemin etkin çözümü için önem taşımaktadır. Son zamanlarda, bazı araştırmacılar çizgenin büyüklüğünü düğümleri ve kenarları birleştirerek küçülten sonra bu küçük çizgeyi parçalayıp sonra orijinal çizge için parçalama oluşturmak için büyüten yeni bir çizge parçalama yöntemleri araştırmaktadırlar. Bu tezde çizge parçalama problemini çözmek için çok seviyeli tasarının küçültme safhasında yeni bir genetik algoritma geliştirilmiş ve denenmiştir.
Özet (Çeviri)
ABSTRACT MULTILEVEL GRAPH PARTITIONING: AN EVOLUTIONARY APPROACH Küçükpetek, Süheyda M.S., Department of Computer Engineering, Supervisor: Assoc. Prof. Dr. Faruk Polat September 2000, 76 pages Balanced graph partitioning problem is defined as dividing the vertices of an undirected graph into sets of balanced components through the removal of a set of nodes or edges, whose sizes are to be minimized. The solution to the problem is central in obtaining efficient solutions for many problems such as VLSI circuit design, load balancing in multiprocessor systems, nested dissection algorithm, and task scheduling. Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges (coarsening), partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this thesis a new genetic algorithm for the coarsening phase of multilevel scheme for solving the graph-partitioning problem is developed and tested.
Benzer Tezler
- Multilevel heuristics for task assignment in distributed systems
Dağıtık sistemlerde çok düzeyli görev atama algoritmaları
MURAT İKİNCİ
Yüksek Lisans
İngilizce
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Çizge algoritmaları ve çizge bölmeleme
Graph algorithms and graph partitioning
ALİ KARCI
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AHMET ARSLAN
- Durağan olmayan kanallarda uyarlamalı hata kontrol yöntemleri
Adaptive coding schemes for time-varying channels
ERSİN ERGEZER
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. H. ÜMİT AYGÖLÜ
- 19. yüzyıl İstanbul dizi konutlarının morfolojik andizine dayalı bilgi tabanlı tasarım modeli
Başlık çevirisi yok
ÇİLER KIRŞAN