Primjena heurističkih algoritama u particiji grafova

undergraduate thesis

• Title (english): Application of Heuristic Algorithms in Graph Partition
• Author: Luka Golić
• Mentor: Tomislav Burić (mentor)
• Committee member: Tomislav Burić (predsjednik povjerenstva)
• Committee member: Ilko Brnetić (član povjerenstva)
• Committee member: Josipa Pina Milišić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-09-17, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovome radu se opisuju algoritmi koji koriste heurističke funkcije za particioniranje grafova. Na primjeru izgradnje integriranih čipova je osviještena važnost tog područja računarske znanosti. Prvo je opisan Kernighan-Lin algoritam. Jedan od najstarijih heurističkih algoritama široko korišten. Opisani su njegovi nedostatci koje pokriva iduće navedeni algoritam, Fiduccia-Mattheyses. Ta dva algoritma su detaljno opisana i pojašnjena na konkretnom primjeru. Spektralno te višerazinsko particioniranje su također objašnjeni jer su danas najraširenije metode za particioniranje grafova. Radi njihove široke familije algoritama i matematičke složenosti ovdje nisu razmatrani na razini detalja. Stoga su ta dva algoritma opisana na konceptualnoj razini uz navođenje osnovnih pojmova potrebna za osnovno shvaćanje rada.

Abstract (english)

In this paper the algorithms which use heuristic functions for partitioning of graphs are being described. The importance of that area of computer science is shown in the example of the construction of integrated chips. First is described Kernighan-Lin algorithm - it's one of the oldest heuristic algorith with widespread use. The next one described is Fiduccia-Mattheyses - this one covers the flaws of the Keenighan-Lin algorithm. These two are minutely described and explained on the concrete example. Spectral and multilevel potentiation are also explained because of theire widespread use in potentiation of graphs. Because of theire wide family of algorithms and mathematical complexity in this paper they are not observed in large details. For that reason these two algorithms are described on conceptual level with basic terms necessary for understanding.

• Keywords: Graf; Hipergraf; Particioniranje; veličina reza grafa; VLSI; Kernighan-Lin; Fiduccia-Mattheyses; Spektralno particioniranje; Višerazinsko particioniranje
• Keywords (english): Graph; Hypergraph; Partitioning; Cut-size; VLSI; Kernighan-Lin; Fiduccia-Mattheyses; Spectral partitioning; Multi-level partitioning
• Language: croatian
• URN:NBN: urn:nbn:hr:168:058733
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 18:10:08