16.
sep
Zagovor diplomskega dela: Jan Kenda
ob 10:00

Naslov diplomskega dela: Hitro 3-barvanje omejenih ravninskih grafov

 

Povzetek:

V delu obravnavamo problem 3-barvanja ravninskih grafov brez ciklov dolžin med 4 in 9. Salavatipour (The Discharging Method in Practice, 2006) je skupaj z dokazom 3-obarvljivosti teh grafov implicitno zapisal tudi kvadratičen algoritem 3-barvanja. V delu predstavimo postopek prenosa naboja, ki je osnovna ideja takega algoritma. Hkrati z natančnejšo strukturno analizo pokažemo, da je moč omenjeni algoritem poenostaviti in hkrati pohitriti. Tako izboljšani algoritem je celo linearne časovne zahtevnosti, kar tudi empirično preverimo.

 

Termin zagovora: ponedeljek, 16. 9. 2019, ob 10.00

 

Lokacija zagovora: Predavalnica 2

 

Mentor: prof. dr. Gašper Fijavž

 

Komisija za zagovor:

prof. dr. Bojan Orel (predsednik),

prof. dr. Gašper Fijavž (mentor),

izr. prof. dr. Polona Oblak (članica).

prof. dr. Marko Petkovšek (član FMF).