Pohlepni algoritmi za bojanje vrhova grafova

završni rad

• Naslov (engleski): Greedy Algorithms for graph vertex coloring
• Autor: Marko Bukal
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (č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: 2016-09-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovome završnom radu proučava se bojanje grafova postupkom pohlepnog bojanja i primjenom sekvencijskih strategija FF, LDO, IDO i SDO. Navedene strategije se uspoređuju s obzirom na vrijeme izvođenja, udaljenost od optimalnog rješenja te na kompleksnost implementacije. Algoritmi se testiraju na DIMACS bazi grafova.

Sažetak (engleski)

In this final thesis we study the classical graph coloring problem and we try to solve it algorithmically using greedy coloring and adequate sequential strategies like FF, LDO, IDO and SDO. We compare different strategies from the aspect of implementation complexity, time complexity and solution approximation quality. In order to do that, we test our algorithms using DIMACS database of simple graphs created for graph coloring experimentation.

• Ključne riječi: bojanje grafova; pohlepno bojanje; sekvencijske strategije
• Ključne riječi (engleski): graph coloring; greedy coloring; sequential strategies
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:167262
• 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 08:05:41