Geri Dön

Graph and hypergraph partitioning

Çizge ve hiperçizge parçalama

  1. Tez No: 29949
  2. Yazar: ALİ DAŞDAN
  3. Danışmanlar: YRD. DOÇ. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111, Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111
  7. Yıl: 1993
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 141

Ö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

  1. Tez No

    541572

    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

    İngilizce

    2018

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  2. Tez No

    180631

    Web-site-based partitioning techniques for efficient parallelization of the pagerank computation

    Sayfadeğeri hesaplamasının etkin olarak paralelleştirilmesi için ağ sitesi tabanlı bölümleme yöntemleri

    ALİ CEVAHİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  3. Tez No

    184698

    Page-to-processor assignment techniques for parallel crawlers

    Paralel ağ tarayıcıları için sayfa atama yöntemleri

    ATA TÜRK

    Yüksek Lisans

    İngilizce

    İngilizce

    2004

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  4. Tez No

    83743

    Partitioning sparse rectangular matrices for parallel computing of AATx

    Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması

    BORA UÇAR

    Yüksek Lisans

    İngilizce

    İngilizce

    1999

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

    Bilgisayar Yazılımı Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  5. Tez No

    335604

    Independent task assignment for heterogeneous systems

    Heterojen sistemler için bağımsız iş atama

    ERTUĞRUL KARTAL TABAK

    Doktora

    İngilizce

    İngilizce

    2013

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

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

Geri Dön