Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
Uvažujeme problém nalezení 2-faktoru v orientovaném grafu se zakázanými přechody v případě, že grafu zakázaných přechodů patří do předepsané třídy C. Popisujeme třídy grafů C, pto které je problém NP-úplný.
V ostatních případech zkonstruujeme polynomiální algoritmus.