Výpočetní složitost dlouhých cest a cyklů v hyperkrychlích s chybami

Abstrakt

Práce studuje složitost problému existence dlouhých (optimálních) cyklů v n-rozměrné hyperkrychli s vadnými vrcholy. Problém je NP-těžký i v případě, kdy je počet chyb omezen polynomem stupně tři (šest) vzhledem k n.

Na druhé straně existuje lineární (kvadratická) mez na počet chyb, která zaručuje, že problém je rozhodnutelný v polynomiálně omezeném čase. Podobné výsledky jsou získány pro cesty i cesty mezi zadanými dvojicemi vrcholů.

Klíčová slova

• Dlouhé cesty
• dlouhé cykly
• hyperkrychle
• vadný vrchol
• NP-těžký problém