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

završni rad

• Naslov (engleski): Solving the extended graph coloring problem using metaheuristic methods
• Autor: Mateo Šimonović
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Marko Čupić (član povjerenstva)
• Član povjerenstva: Domagoj Alagić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: bojanje grafova; metaheuristika; evolucijski algoritam; inteligentne kapi vode; simulirano kaljenje; genetski algoritam
• Ključne riječi (engleski): graph coloring; metaheuristics; evolutionary algorithm; intelligent water drops; simulated annealing; genetic algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:692425
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 12:17:49