Seminár z teoretickej informatiky - Robert Lukoťka (7.12.2018)

v piatok 7.12.2018 o 11:00 hod. v miestnosti M/213

04. 12. 2018 11.52 hod.
Od: Rastislav Královič

Prednášajúci: Robert Lukoťka

Názov: Algoritmus na rozhodnutie hranovej 3-zafarbiteľnosti kubického grafu

Termín: 7.12.2018, 11:00 hod., M/213

Abstrakt:
Zistiť či daný kubický graf má hranové 3-farbenie je známy NP-úplný problém. V prednáške si ukážeme, ako možno rozhodnúť o 3-zafarbiteľnosti kubického grafu na n vrcholoch v čase O(1.201^n). V rovnakom čase je možné riešiť aj niekoľko iných súvisiacich problémov. Základnou ingredienciou pre naše výsledky je algoritmus pre nájdenie cestovej dekompozície so šírkou nanajvýš (1/6+varepsilon).n [F.~V.~Formin, K.~Ho ie: Pathwidth of cubic graphs and exact algorithms, Information Processing Letters 97 (2006) 191--196].

Výsledok vznikol ako spoločná práca skupiny na problémovom seminári KAMAK 2018.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php