Usporedba algoritama za nalaženja maksimalne klike u grafu

završni rad

• Naslov (engleski): Comparison of algorithms for finding the maximal clique in a graph
• Autor: Fran Meglić
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Iva Manojlović (član povjerenstva)
• Član povjerenstva: Matija Livaić (č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: 2024-07-09, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom završnom radu bavili smo se problemom nalaženja maksimalne klike u grafu,
koji je važan problem u teoriji grafova i računarstvu te se često pojavljuje u primjeni, npr.
u područjima bioinformatike i obradi slike.
Opisan je i implementiran algoritam MCQ, te je uspoređen s nekoliko poznatih algoritama za nalaženje maksimalne klike, uključujući MC algoritam Torstena Fahle, BBMC
algoritam Pabla San Segunda, Cliquer Patricka Östergårda i MaxCliqueDyn Janeza Konca.
Provedena je analiza performansi ovih algoritama na DIMACS skupu grafova. Rezultati
su pokazali da algoritam MCQ nudi konkurentne performanse u odnosu na druge algoritme, posebice u slučajevima velikih i gustih grafova

Sažetak (engleski)

In this thesis, we addressed the problem of finding the maximum clique in a graph, an
important problem in graph theory and computer science that frequently appears in applications, particularly in fields such as bioinformatics and image processing. The MCQ
algorithm is described and implemented, and it is compared with several well-known algorithms for finding the maximum clique, including the MC algorithm by Torsten Fahle,
the BBMC algorithm by Pablo San Segundo, the Cliquer algorithm by Patrick Östergård,
and the MaxCliqueDyn algorithm by Janez Konc. Performance analysis of these algorithms was conducted on the DIMACS benchmark graphs. The results showed that
the MCQ algorithm offers competitive performance compared to other algorithms, especially in the cases of large and dense graphs.

• Ključne riječi: Problem maksimalne klike; MCQ algoritam; Cliquer; MaxCliqueDyn; BBMC; DIMACS skup podataka
• Ključne riječi (engleski): Maximum Clique Problem; MCQ algorithm; Cliquer; MaxCliqueDyn; BBMC; DIMACS benchmark graphs
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:119161
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2024-10-12 21:33:23