• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Degree-bounded minimum spanning trees
【24h】

Degree-bounded minimum spanning trees

机译：度限最小生成树

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

摘要

Given n points in the Euclidean plane, the degree- minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most . The problem is NP-hard for 2 3, while the NP-hardness of the problem is open for D 4. The problem is polynomial-time solvable when D 5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean boundeddegree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177–194], we show that, for any arbitrary collection of p oints in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most . p 2 C 2/=3 < 1:1381 times the weight of an MST.
机译：给定欧几里得平面中的n个点，最小度生成树（MST）问题要求最小权重的生成树，其中每个顶点的度最大为。对于2 3，问题是NP困难的，而对于D 4是问题的NP困难的。当D 5时，问题是多项式时间可解决的。通过对Chan的4级MST算法[T提出改进的近似分析。 Chan，欧几里得有界度生成树比率，Discrete＆Computational Geometry 32（2004）177–194]，我们表明，对于欧几里得平面中任意点的点集，总存在最多4次权重的生成树。 p 2 C 2 / = 3 <1：1381乘以MST的重量。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号