On Restricted Two-Factors
On Restricted Two-Factors
复制标题
论受限二因素
DOI：
--
复制
发表时间：
1988
影响因子：
0.8
通讯作者：
I. Kríz
中科院分区：
文献类型：
--
作者：
P. Hell;D. Kirkpatrick;Jan Kratochvíl;I. Kríz
G的双因子由覆盖V(G)$的不相交环组成。作者考虑了双因子的存在性问题，其中环的长度被限制在一个规定的（可能是无限的）整数集合中。给出了由G - u$和G - v $的存在性推导出G中这类受限二因子存在的定理。这些定理的可能性与相应的存在性问题的复杂性相关。特别是，只有四种情况下，多项式算法可以预期（在这个意义上，所有其他情况都显示为np困难）被确定。
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.