Hibridni algoritmi za barvanje grafov

magistrsko delo

Martin Duh (Avtor), Aleksander Vesel (Mentor)

Povzetek

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.

Ključne besede

algoritmi;grafi;barvanje grafov;lokalno iskanje;variabilno lokalno iskanje;evolucijski algoritmi;hibridni algoritmi;magistrska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2016
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[M. Duh]
UDK:	004.421.2:519.174.7(043.2)
COBISS:	21896456
Št. ogledov:	1212
Št. prenosov:	112
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Hybrid algorithms for graph coloring
Sekundarni povzetek:	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.
Sekundarne ključne besede:	algorithms;graphs;graph coloring;local search;variable neighborhood search;evolutionary algorithms;hybrid algorithms;master theses;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	IX, 48 f.
ID:	9115821