Seminar za teorijsko računarstvo
lokacija:
PMF Matematički odsjek
vrijeme:
09.04.2018 - 15:00 - 16:30
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
9. travnja 2018. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo te njezine
studentice Valentina Gavranić i Maja Tonček održat će predavanje pod
naslovom:
"Problem pronalaska klike s najvećom težinom".
Sažetak: Promatra se problem traženja klike s najvećom težinom u grafu.
Klika nekog grafa je podskup vrhova tog grafa sa svojstvom da je inducirani
podgraf tog podskupa potpun. Navedeni problem je NP-težak. U seminaru se
problem rješava pomoću dva algoritma: varijante algoritma "local search with
strong configuration checking" (LSCC) s hill climbingom za manje grafove te
algoritma s heuristikom "dynamic best multiple selection" za veće grafove.
Dobiveni rezultati uspoređuju se s rezultatima algoritama LSCC na grafovima
iz biblioteka DIMACS i BHOSLIB te njegovim varijantama "best from multiple
selection" na grafovima s Network Data Repositoryja.
Pozivaju se svi članovi Seminara kao i ostali zainteresirani da prisustvuju
ovom predavanju.
Robert Manger