izpis_h1_title_alt

Hitro 3-barvanje omejenih ravninskih grafov
Kenda, Jan (Avtor), Fijavž, Gašper (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (431,61 KB)

Izvleček
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 (mb11)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2019
COBISS.SI-ID:1538394819 Povezava se odpre v novem oknu
Število ogledov:171
Število prenosov:72
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

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

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj