Meno:Michal
Priezvisko:Anderle
Názov:Analýza algoritmov pre L(2,1) farbenie grafov
Vedúci:RNDr. Michal Forišek, PhD.
Rok:2016
Blok:INF
Kľúčové slová:L(2,1)-farbenie, vlastné páry, stromy s priemerom 6
Abstrakt:Problém L(2,1)-farbenia je najskúmanejší problém grafového farbenia obmedzeného vzájomnou vzdialenosťou vrcholov. V roku 2012 predstavil Junosza-Szaniawski a kolektív dosiaľ najrýchlejší algoritmus riešiaci tento problém. Ako sa ukázalo, jeho časová zložitosť bola lineárna od počtu vlastných párov v danom grafe. Ostávalo však otvoreným problémom, koľko najviac vlastných párov môže mať graf s n vrcholmi, poznalo sa iba dolné ohraničenie \Omega(2.6117^n) a horné ohraničenie O(2.6488^n). V našej práci sa preto budeme venovať problému najväčšieho počtu vlastných párov. Zameriame sa na stromy s priemerom 6, pre ktoré dokážeme túto hodnotu asymptoticky presne -- \Theta(6048^{n/9}) čo je zhruba \Theta(2.63135^n). S využitím techník prezentovaných pri stromoch s priemerom 6 následne nájdeme triedu grafov, ktorá udá lepšiu dolnú hranicu \Omega(2.63916^n).

Súbory diplomovej práce:

anderle-diplomova-praca.pdf