Jezik: | Slovenski jezik |
---|---|
Leto izida: | 2019 |
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 |
Št. ogledov: | 538 |
Št. prenosov: | 156 |
Ocena: | 0 (0 glasov) |
Metapodatki: |
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 |