Publication at Faculty of Mathematics and Physics |
2009
Abstract
We consider the problem of finding 2-factors in directed graphs with forbidden transitions, in the case that the graphs of forbidden transitions belong to a prescribed class C. We provide an exact characterisation of classes C for that the problem is NP-complete, and show that it is polynomial otherwise.