| 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).
|
|---|