Hibridni algoritmi za barvanje grafov

Duh, Martin

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Hibridni algoritmi za barvanje grafov
Authors:	ID Duh, Martin (Author) ID Vesel, Aleksander (Mentor) More about this mentor...
Files:	MAG_Duh_Martin_2016.pdf (715,10 KB) MD5: 87E3E6D26735D7F0C5A483469942EC4C
Language:	Slovenian
Work type:	Master's thesis/paper
Typology:	2.09 - Master's Thesis
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	Tema magistrskega dela je barvanje grafov s pomoˇcjo hibridnih algoritmov. V magistrskem delu predstavimo algoritem za barvanje grafa z variabilnim lokalnim iskanjem in hibridni algoritem za barvanje grafa, ki združuje evolucijski algoritem z lokalnim iskanjem. Nazadnje še predstavimo hibridni algoritem za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. Magistrsko delo je razdeljeno v osem sklopov. V prvem sklopu so navedeni osnovni pojmi in definicije. V drugem sklopu sledi pregled hevristiˇcnih metod za barvanje grafa. V tretjem sklopu je opisan standardni algoritem za variabilno lokalno iskanje. V ˇcetrtem sklopu je predstavljen prilagojen algoritem za variabilno lokalno iskanje za optimizacijski problem barvanja grafa. V petem sklopu so predstavljeni evolucijski algoritmi. V šestem sklopu so predstavljeni splošni hibridni algoritmi za barvanje grafa. Sklop zakljuˇcimo s hibridnim algoritmom za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. V sedmem sklopu je opis programa v programskem jeziku C++. V zadnjem sklopu so predstavljeni rezultati algoritmov za reševanje problema barvanja grafa na nekaterih izbranih primerih.
Keywords:	algoritmi, grafi, barvanje grafa, lokalno iskanje, variabilno lokalno iskanje, evolucijski algoritmi, hibridni algoritmi
Place of publishing:	Maribor
Publisher:	[M. Duh]
Year of publishing:	2016
PID:	20.500.12556/DKUM-57048
UDC:	004.421.2:519.174.7(043.2)
COBISS.SI-ID:	21896456
NUK URN:	URN:SI:UM:DK:E4PC6S81
Publication date in DKUM:	15.02.2016
Views:	2012
Downloads:	183
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:	English
Title:	Hybrid algorithms for graph coloring
Abstract:	This thesis focuses on graph coloring with the use of hybrid algorithms. In the work we present the algorithm for graph coloring with variable neighborhood search as well as the hybrid algorithm for graph coloring, which unites evolutionary algorithm and local search. Last but not the least we present hybrid algorithm for graph coloring that operates according to the variable neighborhood search principle. This master thesis is divided into eight parts. In the first part, we describe basic concepts and definitions. Following in the second part is an overview of heuristic methods for graph coloring. The third part describes standard variable neighborhood search algorithm. The fourth part presents adapted variable neighborhood search algorithm for the graph coloring optimization problem. In the fifth part, evolutionary algorithms are described. In the sixth part, hybrid algorithms for graph coloring are presented. We conclude this part with the hybrid algorithm for graph coloring that operates according to the variable neighborhood search principle. In the seventh part, the program description in the programming language C++ is presented, and in the final part, the results of algorithms for solving the graph coloring problems are presented.
Keywords:	algorithms, graphs, graph coloring, local search, variable neighborhood search, evolutionary algorithms, hybrid algorithms

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back