Algoritmi za particioniranje grafova

master's thesis

• Author: Ana Iveković
• Mentor: Zvonimir Bujanović (mentor)
• Committee member: Zvonimir Bujanović (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Vjeran Hari (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Particioniranje grafa optimizacijski je problem na koji je moguće svesti velik broj problema iz stvarnog svijeta, na primjer optimizaciju transportne mreže, segmentiranje slika i analizu društvenih mreža. U ovom je radu opisan sam problem, s naglaskom na težinske grafove u kojima su svi vrhovi jednake težine. Definirani su pojmovi usko povezani s problemom, poput sparivanja na grafu, reza, vanjske i unutarnje povezanosti vrhova te ravnoteže particije. Kako se radi o NP-teškom problemu, rješavanje se provodi heurističkim i aproksimacijskim algoritmima. U radu je opisan algoritam spektralnog particioniranja te višerazinska metoda, unutar koje su opisani algoritmi iterativno sažimanje grafa te profinjavanje particije s viših razina na niže. Među tim se algoritmima nalazi i jedan od poznatijih algoritama za biparticioniranje, algoritam Kernighana i Lina, te njegovo poboljšanje, algoritam Fiduccie i Mattheysesa. U opisima je dan osvrt na probleme u kojima postoji uvjet na ravnotežu završne particije te na probleme u kojima takav uvjet ne postoji. U završnom dijelu rada implementirani su neki od opisanih algoritama i uspoređene su njihove performanse na potpuno povezanim težinskim grafovima s jednakom težinom vrhova.

Abstract (english)

Graph partitioning is an optimization problem which can be used to solve many real-world problems, such as transportation network optimization, image segmentation and social networks analysis. This thesis focuses on partitioning of weighted graphs with equally weighted vertices. The key notions of graph matching, cut function, external and internal cut and balance of a partition are defined and explained. Graph partitioning problems are typically NP-hard, therefore, in order to solve them one needs to use heuristic and approximation algorithms. In this thesis several such algorithms are described, namely spectral partitioning algorithm and multilevel method. For the multilevel method, we describe algorithms for iterative coarsening of the graph, as well as algorithms for refining the partition obtained at the lower level to the higher level. Some of the well-known bipartitioning algorithms can be found there, such as the Kernighan-Lin algorithm and its improvement, the Fiduccia-Mattheyses algorithm. Solving techniques are described both from constrained and unconstrained partitioning point of view. In the final chapter an implementation for some of the mentioned algorithm is described. Their performance is compared on fully connected weighted graphs with vertices of equal weight.

• Keywords: particioniranje grafa; optimizacija; algoritam Kernighana i Lina; algoritam Fiduccie i Mattheysesa
• Keywords (english): graph partitioning; optimization; Kernighan-Lin algorithm; Fiduccia-Mattheyses algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:574134
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-05-14 10:27:18