diplomsko delo
Jan Kenda (Avtor), Gašper Fijavž (Mentor)

Povzetek

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.

Ključne besede

ravninski grafi;barvanje grafov;metoda prenosa naboja;računalništvo;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Kenda]
UDK: 004:51(043.2)
COBISS: 1538394819 Povezava se bo odprla v novem oknu
Št. ogledov: 538
Št. prenosov: 156
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Efficient 3-coloring of a subclass of planar graphs
Sekundarni povzetek: 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.
Sekundarne ključne besede: planar graphs;graph coloring;discharging method;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000407
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 34 str.
ID: 11225335
Priporočena dela:
, zbirnik za spletne brskalnike
, diplomsko delo
, diplomsko delo