Algoritmi za distribuirano bojanje grafova

diplomski rad

• Naslov (engleski): Distributed graph coloring algorithms
• Autor: Sven Radovinović
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2022-07-04, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu opisuju se i performansno analiziraju algoritmi za distribuirano bojanje grafova. Predstavljeni su Kuhn-Watternhoferov algoritam, Cole-Vishkinov algoritam i jedan algoritam za defektno bojanje. Performanse su testirane u sinkronom, višeprocesnom i distribuiranom okruženju, gdje je distribuirano okruženje potpomognuto Apache Kafkom.

Sažetak (engleski)

In this thesis distributed graph coloring algorithms are shown and their performances are measured. Algorithms that are shown are Kuhn-Watternhofers algorithm, Cole-Vishkins algorithm and an algorithm for defective coloring. Performances are tested in a synchronous, multiprocessing and distributed mode of work, where the distributed mode is distributed using Apache Kafka.

• Ključne riječi: Teorija grafova; Bojanje grafova; Bojanje vrhova grafa; Distribuirani algoritmi; Distribuirani algoritmi za bojanje grafova; Cole-Vishkinov algoritam; Kuhn-Watternhoferov algoritam; Defektna bojanja; Kafka; Docker
• Ključne riječi (engleski): Graph theory; Graph coloring; Graph vertex coloring; Distributed algorithms; Distributed algorithms for graph coloring; Cole-Vishkin algorithm; Kuhn-Watternhofer algorithm; Defective coloring; Kafka; Docker
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:651193
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 21:30:56