Usporedba pohlepnih algoritama za bojanje grafova

undergraduate thesis

• Title (english): Greedy algorithms comparison for graph coloring
• Author: Antonio Kutnjak
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Josip Žubrinić (član povjerenstva)
• Committee member: Vlatko Crnković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Ovaj rad opisuje dva algoritma bojanja grafova, SLF i SL, njihovu implementaciju,
složenost i optimalnost. Prvo su opisani općeniti pojmovi koji se susreću u teoriji
grafova i ideja pohlepnog algoritma bojanja. Nakon toga su kratko opisani algoritmi
FF i LF koji su baza za glavne algoritme ovog rada. Slijedi detaljan opis algoritama
SLF i SL, njihova implementacija i složenost. Usporedba algoritama je napravljena
na DIMACS grafovima gdje je analizirana optimalnost i potrebno vrijeme izvod̄enja.
Kratko su opisani korišteni razvojni okvir Qt koji je korišten pri izradi vizualizacije
i programski jezik C++ u kojem su implementirani svi algoritmi spomenuti u ovom
radu.

Abstract (english)

This thesis describes two graph coloring algorithms, SLF and SL, their implementation, complexity and optimality. Firstly, general concepts that are encountered in graph theory and the idea of a greedy coloring algorithm are described. After that, the FF and LF algorithms, which are the basis for the main algorithms of this thesis, are briefly described. This is followed by a detailed description of the SLF and SL algorithms, their implementation and complexity. The comparison of the algorithms is made on DIMACS graphs where optimality and the required execution time are analyzed. The Qt framework used in the development of the visualization and the C++ programming language in which all the algorithms mentioned in this thesis are implemented
are briefly described.

• Keywords: diskretna matematika; teorija grafova; bojanje grafova; pohlepni algoritmi; Qt; C++
• Keywords (english): discrete mathematics; graph theory; graph coloring; greedy algorithms; Qt; C++
• Language: croatian
• URN:NBN: urn:nbn:hr:168:926359
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:15:54