...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >The internal Steiner tree problem: Hardness and approximations
【24h】

The internal Steiner tree problem: Hardness and approximations

机译：内部Steiner树问题：硬度和近似值

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

摘要

Given a graph C = (V, E) with a cost function c : E → R~+ and a vertex subset R c V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost ∑_[(u,v)∈E(T)] c(u, v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2p + 1)-approximation algorithm for solving the problem on complete graphs, where ρ is an approximation ratio for the Steiner tree problem. Currently, the best-known pis In 4+∈ < 1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 7/9-approximation algorithm for the problem.
机译：给定具有成本函数c：E→R〜+的图C =（V，E）和顶点子集R c V，内部Steiner树是一个Steiner树，其中包含R中的所有顶点，并且每个顶点R中的in必须是内部顶点。内部Steiner树问题涉及找到内部Steiner树T，其总成本∑ _ [[（u，v）∈E（T）] c（u，v）为最小。在本文中，我们首先证明内部Steiner树问题是MAX SNP困难的。然后，我们提出一种（2p +1）逼近算法，用于解决完整图上的问题，其中ρ是Steiner树问题的逼近比。当前，最著名的pis In 4 +∈<1.39。此外，对于每个边的成本限制为1或2的情况，我们针对该问题提出了7/9近似算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号