20.500.12556/RUL-110521 Hitro 3-barvanje omejenih ravninskih grafov Efficient 3-coloring of a subclass of planar graphs 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. In the thesis we present the 3-coloring problem of planar graphs without cycles of lengths between 4 and 9. Salavatipour (The Discharging Method in Practice, 2006) has proven that such graphs are 3-colorable and his proof can be directly rewritten as a quadratic-time algorithm. We present the discharging method which is the cornerstone for this algorithm. What is more, we focus on the time-critical part and with a careful analysis show that it is indeed not needed. Thus we invent a linear time 3-coloring algorithm of such graphs and we also evaluate its implementation. ravninski grafi barvanje grafov metoda prenosa naboja planar graphs graph coloring discharging method true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2019-09-16 11:55:17 2019-09-16 11:55:19 2022-08-22 03:44:17 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 23745 1538394819 Kenda_Jan_-_Hitro_3-barvanje_omejenih_ravninskih_grafov.pdf Kenda_Jan_-_Hitro_3-barvanje_omejenih_ravninskih_grafov.pdf 1 1AC2D65BC2B10775CE83605E68E24236 cea1848884782e983d337fa231eada7a6193fca7657b6d86ee6112d12533453f 23dadcc0-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=122189 Fakulteta za računalništvo in informatiko 0 0 0