...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >LEHMAN'S THEOREM AND THE DIRECTED STEINER TREE PROBLEM
【24h】

LEHMAN'S THEOREM AND THE DIRECTED STEINER TREE PROBLEM

机译：雷曼定理和更强的Streener问题

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

摘要

In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403-417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices.
机译：在定向Steiner树问题中，我们给出了有向图，非负弧权重，称为子集的顶点子集和称为根的特殊子集。目标是计算将每个终端连接到根的最小权重定向树。我们研究了经典的定向切割线性规划（LP）公式，该公式对每个圆弧都有一个变量，并且对于将端子与根分开的每个切割都具有约束。定向切割LP积分在什么情况下？在本文中，我们演示了雷曼[Math。Math。计划，第17卷（1979），第403-417页]，为最小的非理想杂波提供了一个框架，可以得出这个问题的答案。具体而言，我们证明了该框架为串并联有向图的最佳树状定理和完整性结果提供了简短的证明。此外，我们使用此框架来证明有向切向线性程序对于无环图并且具有至多两个非终端顶点的有向图是必不可少的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号