Language: | Slovenian |
---|---|
Year of publishing: | 2019 |
Typology: | 2.11 - Undergraduate Thesis |
Organization: | UL FRI - Faculty of Computer and Information Science |
Publisher: | [J. Kenda] |
UDC: | 004:51(043.2) |
COBISS: | 1538394819 |
Views: | 538 |
Downloads: | 156 |
Average score: | 0 (0 votes) |
Metadata: |
Secondary language: | English |
---|---|
Secondary title: | Efficient 3-coloring of a subclass of planar graphs |
Secondary 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. |
Secondary keywords: | planar graphs;graph coloring;discharging method;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma; |
Type (COBISS): | Bachelor thesis/paper |
Study programme: | 1000407 |
Embargo end date (OpenAIRE): | 1970-01-01 |
Thesis comment: | Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Pages: | 34 str. |
ID: | 11225335 |