Hitro 3-barvanje omejenih ravninskih grafov

Kenda, Jan (avtor), Fijavž, Gašper (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: ravninski grafi, barvanje grafov, metoda prenosa naboja
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2019
• PID: 20.500.12556/RUL-110521
• COBISS.SI-ID: 1538394819
• Datum objave v RUL: 16.09.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Efficient 3-coloring of a subclass of planar graphs

Izvleček

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.

• Ključne besede: planar graphs, graph coloring, discharging method