izpis_h1_title_alt

Hitro 3-barvanje omejenih ravninskih grafov
ID Kenda, Jan (Author), ID Fijavž, Gašper (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (431,61 KB)
MD5: 1AC2D65BC2B10775CE83605E68E24236

Abstract
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.

Language:Slovenian
Keywords:ravninski grafi, barvanje grafov, metoda prenosa naboja
Work type:Bachelor thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2019
PID:20.500.12556/RUL-110521 This link opens in a new window
COBISS.SI-ID:1538394819 This link opens in a new window
Publication date in RUL:16.09.2019
Views:883
Downloads:194
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Efficient 3-coloring of a subclass of planar graphs
Abstract:
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.

Keywords:planar graphs, graph coloring, discharging method

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back