...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Minimum restricted diameter spanning trees
【24h】

Minimum restricted diameter spanning trees

机译：最小限制直径的跨树

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

摘要

Let G = (V,E) be a requirement graph. Let d = (d_(ij))_(i,j=1)~n be a length metric. For a tree T denote by d_(T(i,j)) the distance between i and j in T (the length according to d of the unique i - j path in T). The restricted diameter of T, D_T, is the maximum distance in T between pair of vertices with requirement between them. The minimum restricted diameter spanning tree problem is to find a spanning tree T such that the restricted diameter is minimized. We prove that the minimum restricted diameter spanning tree problem is NP-hard and that unless P=NP there is no polynomial time algorithm with performance guarantee of less than 2. In the case that G contains isolated vertices and the length matrix is defined by distances over a tree we prove that there exists a tree over the non-isolated vertices such that its restricted diameter is at most 4 times the minimum restricted diameter and that this constant is at least 3 1/2. We use this last result to present an O(log(n))-approximation algorithm.
机译：令G =（V，E）为需求图。令d =（d_（ij））_（i，j = 1）〜n为长度度量。对于树T，用d_（T（i，j））表示T中i与j之间的距离（根据t中唯一i-j路径的d的长度）。 T的受限直径D_T是成对的顶点之间的最大距离（以T为单位），两个顶点之间有要求。最小受限直径生成树问题是找到生成树T，以使受限直径最小化。我们证明最小约束直径生成树问题是NP难的，除非P = NP，否则没有多项式时间算法可保证性能小于2。在G包含孤立顶点且长度矩阵由距离定义的情况下在树上，我们证明了在非隔离顶点上存在树，使得其限制直径最大为最小限制直径的4倍，并且该常数至少为3 1/2。我们使用最后的结果来表示O（log（n））近似算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号