Ročníkový projekt

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.

Zimný semester

Source files: github
Report: pdf