Graph and hypergraph partitioning
Çizge ve hiperçizge parçalama
- Tez No: 29949
- Danışmanlar: YRD. DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111, Grafikler, Paralel bilgisayarlar, Tümleşik devreler, Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111, Graphics, Parallel computers, Integrated circuits
- Yıl: 1993
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ABSTRACT GRAPH AND HYPERGRAPH PARTITIONING Ali Daşdan M.S. in Computer Engineering and Information Science Advisor: Asst. Prof. Cevdet Aykanat September, 1993 Graph and hypergraph partitioning have many important applications in var ious areas such as VLSI layout, mapping, and graph theory. For graph and hypergraph partitioning, there are very successful heuristics mainly based on Kernighan-Lin's minimization technique. We propose two novel approaches for multiple- way graph and hypergraph partitioning. The proposed algorithms drastically outperform the best multiple-way partitioning algorithm both on randomly generated graph instances and on benchmark circuits. The proposed algorithms convey all the advantages of the algorithms based on Kernighan- Lin's minimization technique such as their robustness. However, they do not convey many disadvantages of those algorithms such as their poor performance on sparse test cases. The proposed algorithms introduce very interesting ideas that are also applicable to the existing algorithms without very much effort.
Özet (Çeviri)
ABSTRACT GRAPH AND HYPERGRAPH PARTITIONING Ali Daşdan M.S. in Computer Engineering and Information Science Advisor: Asst. Prof. Cevdet Aykanat September, 1993 Graph and hypergraph partitioning have many important applications in var ious areas such as VLSI layout, mapping, and graph theory. For graph and hypergraph partitioning, there are very successful heuristics mainly based on Kernighan-Lin's minimization technique. We propose two novel approaches for multiple- way graph and hypergraph partitioning. The proposed algorithms drastically outperform the best multiple-way partitioning algorithm both on randomly generated graph instances and on benchmark circuits. The proposed algorithms convey all the advantages of the algorithms based on Kernighan- Lin's minimization technique such as their robustness. However, they do not convey many disadvantages of those algorithms such as their poor performance on sparse test cases. The proposed algorithms introduce very interesting ideas that are also applicable to the existing algorithms without very much effort.
Benzer Tezler
- Graph/hypergraph partitioning models for simultaneous load balancing on computation and data
Eş zamanlı hesaplama ve veri yükü dengeleme için çizge/hiperçizge bölümleme modelleri
MESTAN FIRAT ÇELİKTUĞ
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Combinatorial reductions between graph partitioning by vertex separator and hypergraph partitioning problems for parallel and scientific computing applications
Paralel ve bilimsel hesaplama uygulamaları için hiperçizge bölümleme ve düğüm ayıracı ile çizge bölümleme problemlerinin birbirine kombinatoriyal dönüştürümü
ENVER KAYAASLAN
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
LEVENT KANDİLLER
Doktora
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ.DR. MUSTAFA AKGÜL
- 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
- 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
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT