Hitro 3-barvanje omejenih ravninskih grafovKenda, Jan (Avtor) Fijavž, Gašper (Mentor) ravninski grafibarvanje grafovmetoda prenosa nabojaV 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.20192019-09-16 11:55:17Diplomsko delo/naloga110521VisID: 23745COBISS_ID: 1538394819sl