Timotej Hrga: Uporaba visokozmogljivega računalništva pri izračunu neodvisnega števila grafa

Na seminarju bo predstavljen eksaktni algoritem za izračun neodvisnega (stabilnega) števila grafa, ki temelji na metodi razveji in omeji (B&B). Gre za problem iz kombinatorične optimizacije, kjer iščemo stabilno množico v grafu z največjo kardinalnostjo. Algoritem združuje tehnike iz semidefinitnega programiranja (SDP) in visokozmogljivega računalništva (HPC). Preiskovalno drevo B&B algoritma pregledujemo paralelno, pri čemer v vsakem vozlišču rešimo SDP relaksacijo problema za določitev zgornje meje optimalne vrednosti originalnega problema. Gostota danega grafa določa izbiro algoritma za reševanje dobljenega semidefinitnega programa. Rezultat je odprto dostopni visokozmogljiv reševalec BiqBin.

Gre za skupno delo z Univerzo v Celovcu (AAU Klagenfurt).