Robert Lukoťka
Toto je zoznam tém, ktoré mám premyslené a pripravé. Okrem týchto tém sú k dispozícii ďalšie, ktoré ale vyžadujú určitú mieru diskusie.
Algoritmy na určenie cirkulárneho chromatického indexu kubických grafov (DP)
Cirkulárne r-farbenie grafu je priradenie farieb hranám, pričom rozdiel farieb susedných hrán musí byť aspoň 1 modulo r. Cieľom práce je preskúmať možnosti na efektívny výpočet circulárneho chromatického indexu kubických a subkubických grafov.
Očakávané nástroje: zmiešané lineárne programovanie, základy topológie.
Nerepetitívne zoznamové farbenia ciest(BP, DP)
Majme cestu na n vrcholoch. Ku kazdemu vrcholu je priradeny zoznam 3 prirodzenych cisel. Hypotéza o zoznamovom nerepetitívnom farbení ciest hovorí, že je vždy možné zo zoznamov vybrať farby tak, že ziadnych 2k susedných vrcholov nebude ofarbených tak, že prvá polka postupnosti je ofarbená rovnako ako druhá polka. Cieľom práce je overiť túto hypotézu pre čo najväčšie n. Diplomová práca A. Stupala dokazuje hypotézu do 11 vrcholov.
Očakávané nástroje: hocičo co pomôže, 15 vrcholov by bol úspech.
Kubické grafy ktorých každá hrana leží v krátkej kružnici (BP, DP)
S kolegami sme nedávno dokázali, že kubické grafy, ktorých každá hrana leží v kružníci dĺžky aspoň 5 sú, okrem Petersenovho grafu, hranovo 3-zafarbiteľné, a teda, pre tieto grafy je problém hranovej 3-zafarbiteľnosti rohodnuteľý v P. Cieľom práce je získať o tejto, a o podobných triedach grafov, nové výsledky o zložitosti najštudovanejšík algoritmických problémov.
Očakávané nástroje: návrh efektívnych algoritmov, štrukturálna analýza, dôkazy NP-ťažkosti
Použitie SAT a ILP solverov pre dokazovanie hypotéz pre triedy grafov (BP, DP)
Za určitých podmienok možno SAT a ILP solvery použiť nie len na dokázanie vlastností jedného objektu, ale v jednej inštancii dokázať, že niečo platí pre celú triedu objektov. Táto téma je pomerne hmlistá, bude treba začať pracovať rýchlo aby sa ukázalo, čo sa týmto smerom dá robiť
Očakávané nástroje: ILP solvery, SAT solvery, matematická logika