Seminár z teoretickej informatiky - Robert Lukoťka (7.12.2018)
v piatok 7.12.2018 o 11:00 hod. v miestnosti M/213
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