...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RAIRO Operation Research >On The Steiner 2-edge Connected Subgraph Polytope
【24h】

On The Steiner 2-edge Connected Subgraph Polytope

机译：在Steiner 2边连通子图多义线上

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs.
机译：在本文中，我们研究了Steiner 2边连接子图多义词。我们为这种多态介绍了一大类有效不等式，称为广义Steiner F分区不等式，它推广了所谓的Steiner F分区不等式。我们表明，这些不等式以及琐碎的和Steiner割的不等式完全描述了概括轮子的一类图上的多面体。我们还描述了定义这些不等式的必要条件，因此，我们获得了可以在多项式时间内解决该类图在Steiner 2边连接的子图多义上的分离问题。此外，我们讨论了通过三边缘割集分解的图中的多表位。并且，我们证明了广义Steiner F分区不等式以及琐碎和Steiner割不等式足以在一类图中描述多边形，该图概括了当终端具有特定配置时的Halin图类。这可以将Barahona和Mahjoub [4]的结果推广到Halin图。这也为该类图中的Steiner 2边连通子图问题提供了多项式时间切面算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号