Show simple item record

dc.contributor.advisorAykanat, Cevdet
dc.contributor.authorDaşdan, Ali
dc.date.accessioned2020-12-02T12:51:19Z
dc.date.available2020-12-02T12:51:19Z
dc.date.submitted1993
dc.date.issued2018-08-06
dc.identifier.urihttps://acikbilim.yok.gov.tr/handle/20.500.12812/37388
dc.description.abstractABSTRACT 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.abstractABSTRACT 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 111en_US
dc.languageEnglish
dc.language.isoen
dc.rightsinfo:eu-repo/semantics/embargoedAccess
dc.rightsAttribution 4.0 United Statestr_TR
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectBilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontroltr_TR
dc.subjectComputer Engineering and Computer Science and Controlen_US
dc.titleGraph and hypergraph partitioning
dc.title.alternativeÇizge ve hiperçizge parçalama
dc.typemasterThesis
dc.date.updated2018-08-06
dc.contributor.departmentDiğer
dc.subject.ytmGraphics
dc.subject.ytmParallel computers
dc.subject.ytmIntegrated circuits
dc.identifier.yokid29949
dc.publisher.instituteMühendislik ve Fen Bilimleri Enstitüsü
dc.publisher.universityİHSAN DOĞRAMACI BİLKENT ÜNİVERSİTESİ
dc.identifier.thesisid29949
dc.description.pages123
dc.publisher.disciplineDiğer


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/embargoedAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/embargoedAccess