Naredni sastanak Seminara biće održan u utorak, 1. aprila 2025. godine, u sali 301f Matematičkog instituta SANU sa početkom u 14.15.
Predavač: Tatjana Davidović, Matematički institut SANU
Naslov predavanja: MAKSIMIZACIJA SPEKTRALNOG RADIJUSA GRAFOVA JE PROBLEM OPTIMIZACIJE
Apstrakt: Grafovi pragova (Threshold Graphs, TG) su važni u teoriji grafova zbog svoje posebne strukture i brojnih primena. Posebno su interesantni TG koji maksimizuju indeks, odnosno najveću sopstvenu vrednost. Karakterizacija maksimizatora radijusa među povezanim TG sa datim brojem vrhova i ivica, u opštem slučaju, još uvek je otvoren problem. Zato je važno da se izvrši računarska enumeracija TG koja bi pomogla istraživačima da naprave i dokažu hipoteze o strukturi maksimizatorskih grafova. Predstavljajući ovo nabrajanje kao kombinatorni problem optimizacije, omogućava korišćenje metaheurističkih metoda, o ovom slučaju, opšte metode promenljivih okolina (General Variable Neighborhood Search, GVNS) i metode optimizacije kolonijom pčela zasnovane na poboljšanju postojećih rešenja (improvement-based Bee Colony Optimization, BCOi). VNS metoda se oslanja na iterativna poboljšanja jednog trenutnog najboljeg rešenja, dok je BCO zasnovana na populaciji rešenja i pripada klasi metoda inteligencije roja (Swarm Intelligence, SI). Koristi se kompaktna reprezentacija rešenja i nekoliko pomoćnih struktura podataka koje treba da omoguće efikasnu pretragu prostora rešenja. Pored toga, definisano je nekoliko vrsta transformacija koje čuvaju dopustivost rezultujućeg rešenja. Preliminarni rezultati na primerima srednje veličine pokazali su da su sistematičnije pretrage koje izvršava GVNS nešto efikasnije od nasumičnih modifikacija koje su korišćene u okviru BCOi. Međutim, verovatno je da bi se obe metode mogle poboljšati i to je tema tekućih istraživanja na ovu temu.
Izlaganje predstavlja rezultate rada u okviru projekta #6767: Lazy walk counts and spectral radius of graphs—LZWK, Fonda za nauku Republike Srbije i letnje studentske istraživačke prakse, Matematičkog instituta SANU. Koautori su Dragan Stevanović, Luka Radanović, Abdelkadir Fellague i Dragutin Ostojić.
Napomena: Predavanja na Seminaru se snimaju i prenose uživo.
Sve informacije mogu se naći na stranici
https://miteam.mi.sanu.ac.rs/asset/qGapAHyEBad2FDwXR
