Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
Článek se zabývá dlouhými cestami v n-rozměrné hyperkrychli, která se vyhýbají zadané množině vadných vrcholů. Hlavním výsledkem práce je algoritmus, který pro nejvýše kvadratický počet chyb určí, zdali mezi zadanou dvojicí vrcholů existuje dlouhá cesta, a to v polynomiálním čase vzhledem k n.
V kladném případě navíc cestu sestrojí v lineárním čase vzhledem k její délce.