• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Facets of the (s, t)-p-path polytope
【24h】

Facets of the (s, t)-p-path polytope

机译：（s，t）-p路径多态性的方面

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

摘要

We give a partial description of the (s, t)-p-path polytope of a directed graph D which isthe convex hull of the incidence vectors of simple directed (s, t)-paths in D of length p.First, we point out how the (s, t)-p-path polytope is located in the family of path and cyclepolyhedra. Next, we give some classes of valid inequalities which are very similar to theinequalities which are valid for the p-cycle polytope, that is, the convex hull of the incidencevectors of simple cycles of length p in D. We give necessary and sufficient conditions forthese inequalities to be facet defining. Furthermore, we consider a class of inequalities thathas been identified to be valid for (s, t)-paths of cardinality at most p. Finally, we transferthe results to related polytopes, in particular, the undirected counterpart of the (s, t)-p-path polytope.
机译：我们给出了有向图D的（s，t）-p路径多边形的部分描述，该图是长度为p的D中简单有向（s，t）路径的入射向量的凸包。找出（s，t）-p路径多态性在路径和循环多面体家族中的位置。接下来，我们给出一些有效不等式，这些有效不等式与对于p循环多态性有效的不等式非常相似，也就是D中长度为p的简单循环的入射向量的凸包。我们给出了必要的充分条件不平等的定义。此外，我们考虑一类不等式，这些不等式已被确定对于最多为p的基数的（s，t）路径有效。最后，我们将结果转移到相关的多表位，特别是（s，t）-p路径多表位的无向对应物。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号