| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Hevristični algoritem za 3-barvanje grafov
Authors:ID Arnečič, Luka (Author)
ID Taranenko, Andrej (Mentor) More about this mentor... New window
Files:.pdf MAG_Arnecic_Luka_2015.pdf (860,06 KB)
MD5: 4039D7A3156B7D93AF23B4B4CED75FF3
 
Language:Slovenian
Work type:Master's thesis/paper (mb22)
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Magistrsko delo obravnava hevristični algoritem za 3-barvanje grafov, ki temelji na hibridiziranem evolucijskem algoritmu in se lahko uporabi za ugotavljanje dobre 3-obarvljivosti navadnih neusmerjenih grafov. Najprej razložimo matematične osnove problema in predstavimo algoritme, na katerih temelji naš hevristični algoritem, nato ga opišemo, na koncu pa predstavimo primerjavo hevrističnega algoritma z algoritmi uporabljenimi in opisanimi v osnovnem članku [9]. V prvem delu razložimo matematične osnove, ki so potrebne za razumevanje problema dobrega 3-barvanja grafov in predstavimo osnovne zasnove algoritmov, na katerih temelji hevristični algoritem. V drugem delu predstavimo hevristični algoritem po komponentah ter podatkovne strukture, ki so uporabljene v hevrističnem algoritmu. Vsako komponento algoritma natančno opišemo in predstavimo idejo, za katero je bila uporabljena. V tretjem delu predstavimo primerjavo hevrističnega algoritma z algoritmi, uporabljenimi in opisanimi v osnovnem članku [9].
Keywords:barvanje grafov, algoritmi na grafih, diskretni algoritmi, hevristike
Year of publishing:2015
Publisher:[L. Arnečič]
Source:Maribor
PID:20.500.12556/DKUM-55549 New window
UDC:004.421.2:519.174.7(043.2)
COBISS.SI-ID:21895944 New window
NUK URN:URN:SI:UM:DK:RX5I2VLV
Publication date in DKUM:15.02.2016
Views:1530
Downloads:156
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
Kopiraj citat
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

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:A heuristic algorithm for graph 3-coloring
Abstract:This thesis focuses on a heuristic algorithm for 3-coloring of graphs, based on hybrid evolutionary algorithm. It can be used for testing, if a normal unidirectional graph can be properly 3-colored. First, we explain the mathematical background of the problem and present the algorithms on which our heuristic algorithm is based on, then we describe the heuristic algorithm itself. At the end, we present a comparison of the heuristic algorithm with algorithms used and described in [9]. In the first part we explain the mathematical basis necessary for the understanding of the problem of proper 3-colorings of graphs and present the basic algortihm concepts on which our heuristic algorithm is based on. In the second part we present the heuristic algorithm by components and data structures used in the heuristic algorithm. We describe each component of the algorithm and present an idea of why it was used. In the third part we present a comparison of a heuristic algorithm with algorithms used and described in [9].
Keywords:coloring of graphs, graph algorithms, nonnumerical algorithms, heuristics


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica