Restricted 2-factors in bipartite graphs
[摘要] The k-restricted 2-factor problem is that of finding a spanning subgraph consisting of disjoint cycles with no cycle of length less than or equal to k. It is a generalization of the well known Hamilton cycle problem and is equivalent to this problem when n2≤k≤n-1 . This paper considers necessary and sufficient conditions, algorithms, and polyhedral conditions for 2-factors in bipartite graphs and restricted 2-factors in bipartite graphs. We introduce a generalization of the necessary and sufficient condition for 4-restricted 2-factors in bipartite graphs to 2k-restricted 2-factors in bipartite graphs of a particular form.
[发布日期] [发布机构] Rice University
[效力级别] Operations research [学科分类]
[关键词] [时效性]