Hibridni algoritmi za barvanje grafov

magistrsko delo

Martin Duh (Author), Aleksander Vesel (Mentor)

Abstract

Tema magistrskega dela je barvanje grafov s pomočjo 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čnih metod za barvanje grafa. V tretjem sklopu je opisan standardni algoritem za variabilno lokalno iskanje. V četrtem 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čimo 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 grafov;lokalno iskanje;variabilno lokalno iskanje;evolucijski algoritmi;hibridni algoritmi;magistrska dela;

Data

Language:	Slovenian
Year of publishing:	2016
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Duh]
UDC:	004.421.2:519.174.7(043.2)
COBISS:	21896456
Views:	1212
Downloads:	112
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Hybrid algorithms for graph coloring
Secondary 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.
Secondary keywords:	algorithms;graphs;graph coloring;local search;variable neighborhood search;evolutionary algorithms;hybrid algorithms;master theses;
URN:	URN:SI:UM:
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	IX, 48 f.
ID:	9115821