Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek
vrijeme: 
10.10.2022 - 15:00 - 17:00

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 10. listopada 2022. u 15 sati,

Robert Manger (PMF-MO, Zagreb) održat će predavanje pod naslovom:

"O računskoj složenosti problema dvostruke rimske dominacije".

Sažetak: Dvostruka rimska dominacija (DRD) je optimizacijski problem koji se zadaje na neusmjerenom grafu. Može se smatrati nadogradnjom klasičnog problema dominirajućeg skupa vrhova ili problema (jednostavne) rimske dominacije. Primjenjuje se u operacijskim istraživanjima, npr. za određivanje optimalnog broja i rasporeda vatrogasnih postrojbi koji će za odabrane lokacije u gradu omogućiti zadovoljavajuću razinu obranjivosti od požara. U ovom predavanju daje se pregled novijih članaka raznih autora koji se odnose na računsku složenost problema DRD. Pokazuje se da je problem NP-težak, i to ne samo u općenitom slučaju nego i za neke specijalnije vrste grafova (npr. planarne ili bipartitne grafove). S druge strane, pokazuje se da postoje i takve vrste grafova (npr. stabla ili intervalni grafovi) gdje se rješenje može dobiti u polinomijalnom vremenu.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 104.

Pozivaju se članovi seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Robert Manger.

Share this