Naredni sastanak Seminara biće održan onlajn u petak, 22. novembra 2024. godine sa početkom u 12 časova.
Predavač: Aleksa Đorđević, Univerzitet u Oksfordu
Naslov predavanja: MINIMALNI REZOVI U GRAFU I GOMORY-HU STABLA
Apstrakt: Minimalan rez u težinskom grafu G=(V,E) je particija skupa čvorova V u podskupove A i B takva da je ukupna težina svih grana između A i B (ali ne i onih unutar A i B) minimalna. U ovom predavanju ćemo se posvetiti ovom problemu iz nekoliko uglova:
1) nalaženje minimalnog (s,t)-reza (reza gde s i t ne pripadaju istom podskupu) i vezom sa maksimalnim protokom u grafu
2) nalaženju globalnog minimalnog reza
3) nalaženju minimalnog (s,t)-reza za sve s, t iz V (Gomory-Hu) stabla
Kroz predavanje ćemo se ukratko osvrnuti na skorašnje napretke u vremenskoj složenosti ovih algoritama, ali nećemo ulaziti u detalje implementacije. Predavanje ne prepostavlja poznavanje bilo kog od ovih problema i algoritama za njihovo rešavanje.
Napomena: Predavanja se mogu pratiti na daljinu preko linka:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Registraciona forma je dostupna na:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73
