Наредни састанак Семинара биће одржан онлајн у петак, 22. новембра 2024. године са почетком у 12 часова.
Предавач: Алекса Ђорђевић, Универзитет у Оксфорду
Наслов предавања: МИНИМАЛНИ РЕЗОВИ У ГРАФУ И GOMORY-HU СТАБЛА
Апстракт: Минималан рез у тежинском графу G=(V,E) је партиција скупа чворова V у подскупове A и B таква да је укупна тежина свих грана између A и B (али не и оних унутар A и B) минимална. У овом предавању ћемо се посветити овом проблему из неколико углова:
1) налажење минималног (s,t)-реза (реза где s и t не припадају истом подскупу) и везом са максималним протоком у графу
2) налажењу глобалног минималног реза
3) налажењу минималног (s,t)-реза за све s,t из V (Gomory-Hu) стабла
Кроз предавање ћемо се укратко осврнути на скорашње напретке у временској сложености ових алгоритама, али нећемо улазити у детаље имплементације. Предавање не препоставља познавање било ког од ових проблема и алгоритама за њихово решавање.
Напомена: Предавања се могу пратити на даљину преко линка:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Регистрациона форма је доступна на:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73