
























Let $G=(V, E)$ be an undirected graph. The subtours elimination polytope $P(G)$ is the set of $x\in \mathbb{R}^E$ such that: $0\leq x(e)\leq 1$ for any edge $e\in E$, $x(δ(v))=2$ for any vertex $v\in V$, and $x(δ(U))\geq 2$ for any nonempty and proper subset $U$ of $V$. $P(G)$ is a relaxation of the Traveling Salesman Polytope, i.e., the convex hull of the Hamiton circuits of $G$. Maurras \cite{Maurras 1975} and Grötschel and Padberg \cite{Grotschel and Padberg 1979b} characterize the facets of $P(G)$ when $G$ is a complete graph. In this paper we generalize their result by giving a minimal description of $P(G)$ in the general case and by presenting a short proof of it.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。