×

On restricted two-factors. (English) Zbl 0672.05065

Summary: A two-factor of G consists of disjoint cycles that cover V(G). The authors consider the existence problem for two-factors in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers. Theorems are presented which derive the existence of such restricted two-factors in G from their existence in G-u and G-v. The possibility of such theorems is then related to the complexity of the corresponding existence problem. In particular, the only four cases in which polynomial algorithms can be expected (in the sense that all other cases are shown to be NP-hard) are identified.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI