Restricted 2-factor polytopes
Restricted 2-factor polytopes
复制标题
限制性二因子多胞形
DOI：
10.1007/s101079900110
复制
发表时间：
2000
影响因子：
2.7
通讯作者：
Yaoguang Wang
中科院分区：
文献类型：
--
作者：
W. Cunningham;Yaoguang Wang
摘要：最优 k 限制 2 因子问题包括在完全无向图 Kn 中找到所有组件都具有超过 k 个节点的最小成本 2 因子（每个节点的度数为 2 的子图）。该问题是著名的对称旅行商问题的松弛，并且在 ≤k≤n−1 时等价。我们研究 k 限制的 2 因子多胞形。我们提出一大类有效的不等式，称为二分不等式，并描述它们的一些属性；其中一些结果甚至对于旅行推销员多面体来说都是新的。对于 k=3 的情况，即无三角形的 2 因子多胞形，我们推导了此类不等式进行面诱导的充分必要条件。
Abstract.The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph Kn, a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing.