Наредни састанак Семинара биће одржан у уторак, 1. априла 2025. године, у сали 301ф Математичког института САНУ са почетком у 14.15.
Предавач: Татјана Давидовић, Математички институт САНУ
Наслов предавања: МАКСИМИЗАЦИЈА СПЕКТРАЛНОГ РАДИЈУСА ГРАФОВА ЈЕ ПРОБЛЕМ ОПТИМИЗАЦИЈЕ
Апстракт: Графови прагова (Threshold Graphs, TG) су важни у теорији графова због своје посебне структуре и бројних примена. Посебно су интересантни TG који максимизују индекс, односно највећу сопствену вредност. Карактеризација максимизатора радијуса међу повезаним TG са датим бројем врхова и ивица, у општем случају, још увек је отворен проблем. Зато је важно да се изврши рачунарска енумерација TG која би помогла истраживачима да направе и докажу хипотезе о структури максимизаторских графова. Представљајући ово набрајање као комбинаторни проблем оптимизације, омогућава коришћење метахеуристичких метода, о овом случају, опште методе променљивих околина (General Variable Neighborhood Search, GVNS) и методе оптимизације колонијом пчела засноване на побољшању постојећих решења (improvement-based Bee Colony Optimization, BCOi). VNS метода се ослања на итеративна побољшања једног тренутног најбољег решења, док је BCO заснована на популацији решења и припада класи метода интелигенције роја (Swarm Intelligence, SI). Користи се компактна репрезентација решења и неколико помоћних структура података које треба да омогуће ефикасну претрагу простора решења. Поред тога, дефинисано је неколико врста трансформација које чувају допустивост резултујућег решења. Прелиминарни резултати на примерима средње величине показали су да су систематичније претраге које извршава GVNS нешто ефикасније од насумичних модификација које су коришћене у оквиру BCOi. Међутим, вероватно је да би се обе методе могле побољшати и то је тема текућих истраживања на ову тему.
Излагање представља резултате рада у оквиру пројекта #6767: Lazy walk counts and spectral radius of graphs—LZWK, Фонда за науку Републике Србије и летње студентске истраживачке праксе, Математичког института САНУ. Коаутори су Драган Стевановић, Лука Радановић, Abdelkadir Fellague и Драгутин
Остојић.
Напомена: Предавања на Семинару се снимају и преносе уживо. Све информације могу се наћи на страници
https://miteam.mi.sanu.ac.rs/asset/qGapAHyEBad2FDwXR