Meno študenta: Ján Gottweis
email: gottweis2@uniba.sk
Vedúci projektu: Jozef Rajník
email: jozef.rajnik@fmph.uniba.sk
Cieľ projektu: Navrhnúť algoritmus, ktorý zistí o zadanom snarku, či je kritický.
Špecifikácia: Snark je 3-regulárny graf bez hranového 3-farbenia. Snark je kritický,
ak po odstránení ľubovoľných dvoch vrcholov dostaneme hranovo 3-zafarbiteľný graf. Doterajšie algoritmy
testujú kritickosť priamočiaro: odstránia postupne každú dvojicu susedných vrcholov a otestujú zafarbiteľnosť
výsledného grafu. Výstupom projektu by mal byť algoritmus, ktorý je aspoň v signifikantnom množstve prípadov
lepší ako priamočiary algoritmus.