Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
复制标题
通过 Padberg-Rao 和紧凑线性程序分离无爪图中的稳定集
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Gautier Stauffer
中科院分区：
文献类型：
--
作者：
Yuri Faenza;G. Oriolo;Gautier Stauffer
在这篇文章中，我们给出了无爪图中稳定集问题的第一个线性规划公式，以及这些公式的多项式时间分离例程(它们不是紧的)。然后，我们利用这些扩展公式之一，提出了一种新的多时间算法来解决无爪图的稳定集多面体的分离问题。这个例程结合了Padberg和Rao提出的匹配多面体的分离算法和(中等大小)紧凑型线性规划的解。因此，它不依赖于椭球方法，似乎适合于插入分支和切割框架来解决现实世界的问题。
In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.