Predavatelj: Aleksander Vesel

Določanje grafovskih invariant je pomemben del teorije grafov. Med zanimivimi invariantami so kromatično število, neodvisnostno število in dominantno število. Znano je, da so problemi določitve teh invariant v poljubnem grafu NP-težki, kljub temu pa je bilo nekaj pomembnih rezultatov iz tega področja pridobljenih s pomočjo računalnika. V predavanju bomo pokazali, kako uspešno uporabimo iskanje v globino (DFS) za določanje invariant produktov s cikli.