Algoritmi za distribuirano bojanje grafova

master's thesis

• Title (english): Distributed graph coloring algorithms
• Author: Sven Radovinović
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Domagoj Kovačević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-04, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: Teorija grafova; Bojanje grafova; Bojanje vrhova grafa; Distribuirani algoritmi; Distribuirani algoritmi za bojanje grafova; Cole-Vishkinov algoritam; Kuhn-Watternhoferov algoritam; Defektna bojanja; Kafka; Docker
• Keywords (english): Graph theory; Graph coloring; Graph vertex coloring; Distributed algorithms; Distributed algorithms for graph coloring; Cole-Vishkin algorithm; Kuhn-Watternhofer algorithm; Defective coloring; Kafka; Docker
• Language: croatian
• URN:NBN: urn:nbn:hr:168:651193
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 21:30:56