prikaz prve stranice dokumenta Usporedba pohlepnih algoritama za bojanje grafova
No public access
undergraduate thesis
Usporedba pohlepnih algoritama za bojanje grafova
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. urn:nbn:hr:168:926359
Kutnjak, Antonio
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Kutnjak, A. (2023). Usporedba pohlepnih algoritama za bojanje grafova (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:926359

Kutnjak, Antonio. "Usporedba pohlepnih algoritama za bojanje grafova." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:926359

Kutnjak, Antonio. "Usporedba pohlepnih algoritama za bojanje grafova." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:926359

Kutnjak, A. (2023). 'Usporedba pohlepnih algoritama za bojanje grafova', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 16 July 2024, https://urn.nsk.hr/urn:nbn:hr:168:926359

Kutnjak A. Usporedba pohlepnih algoritama za bojanje grafova [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2023 [cited 2024 July 16] Available at: https://urn.nsk.hr/urn:nbn:hr:168:926359

A. Kutnjak, "Usporedba pohlepnih algoritama za bojanje grafova", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:168:926359

Metadata
TitleUsporedba pohlepnih algoritama za bojanje grafova
Title (english)Greedy algorithms comparison for graph coloring
AuthorAntonio Kutnjak
MentorMario Osvin Pavčević (mentor)
Committee memberMario Osvin Pavčević (predsjednik povjerenstva)
Committee memberJosip Žubrinić (član povjerenstva)
Committee memberVlatko Crnković (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2023-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:926359
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-07-13 10:15:54