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
Share this