Rješavanje proširenog problema bojanja grafova metaheurističkim postupcima

undergraduate thesis

• Title (english): Solving the extended graph coloring problem using metaheuristic methods
• Author: Mateo Šimonović
• Mentor: Marin Golub (mentor)
• Committee member: Marin Golub (predsjednik povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Committee member: Domagoj Alagić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U radu su predstavljene dvije inačice problema bojanja grafova, klasična i proširena.
Problem proširenog bojanja grafova primjenjiv je u domeni telekomunikacija u
dodjeljivanju jedinstvenih indeksa susjednim ćelijama u LTE mobilnoj mreži. Problem
se obrađuje teorijski i praktično. U teorijskom dijelu detaljno je analiziran problem i
određene su mogućnosti i ograničenja njegove implementacije na računalu. U radu su
dalje objašnjeni različiti metaheuristički postupci, a detaljnije algoritam inteligentnih
kapi vode. Na kraju su prikazani rezultati istraživanja i prijedlog rješenja problema
proširenog bojanja grafova.

Abstract (english)

In this paper are presented two instances of the graph coloring problem, the classic
and an extended one. The extended graph coloring problem can be applied in telecommunication
domain in the process of assigning root sequence indexes to neighbor
cells in an LTE mobile network. The problems are observed both theoretically and
practically. In the theoretical part, the problems have been studied in detail where possibilities
and limitations of their computer implementations are analyzed. Next chapters
describe metaheuristics algorithms and more in detail the Intelligent Water Drops
algorithm. In conclusion, results of this research are shown as well as a proposal for
solving the extended graph coloring problem.

• Keywords: bojanje grafova; metaheuristika; evolucijski algoritam; inteligentne kapi vode; simulirano kaljenje; genetski algoritam
• Keywords (english): graph coloring; metaheuristics; evolutionary algorithm; intelligent water drops; simulated annealing; genetic algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:692425
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 12:17:49