Graph and hypergraph partitioning
dc.contributor.advisor | Aykanat, Cevdet | |
dc.contributor.author | Daşdan, Ali | |
dc.date.accessioned | 2020-12-02T12:51:19Z | |
dc.date.available | 2020-12-02T12:51:19Z | |
dc.date.submitted | 1993 | |
dc.date.issued | 2018-08-06 | |
dc.identifier.uri | https://acikbilim.yok.gov.tr/handle/20.500.12812/37388 | |
dc.description.abstract | 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. Keywords: Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111 | |
dc.description.abstract | 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. Keywords: Graph Partitioning, Hypergraph Partitioning, Circuit Partitioning, Local Search Heuristics, Partitioning Algorithms 111 | en_US |
dc.language | English | |
dc.language.iso | en | |
dc.rights | info:eu-repo/semantics/embargoedAccess | |
dc.rights | Attribution 4.0 United States | tr_TR |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
dc.subject | Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol | tr_TR |
dc.subject | Computer Engineering and Computer Science and Control | en_US |
dc.title | Graph and hypergraph partitioning | |
dc.title.alternative | Çizge ve hiperçizge parçalama | |
dc.type | masterThesis | |
dc.date.updated | 2018-08-06 | |
dc.contributor.department | Diğer | |
dc.subject.ytm | Graphics | |
dc.subject.ytm | Parallel computers | |
dc.subject.ytm | Integrated circuits | |
dc.identifier.yokid | 29949 | |
dc.publisher.institute | Mühendislik ve Fen Bilimleri Enstitüsü | |
dc.publisher.university | İHSAN DOĞRAMACI BİLKENT ÜNİVERSİTESİ | |
dc.identifier.thesisid | 29949 | |
dc.description.pages | 123 | |
dc.publisher.discipline | Diğer |