...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The zoo of tree spanner problems
【24h】

The zoo of tree spanner problems

机译：动物园扳手问题

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

摘要

Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of max-stretch tree spanner problems and of average stretch tree spanner problems. We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems. Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati [On min-max cycle bases, in: P. Eades, T. Takaoka (Eds.), ISAAC, Lecture Notes in Computer Science, vol. 2223, Springer, Berlin, 2001, pp. 116-123; On finding cycle bases and fundamental cycle bases with a shortest maximal cycle, Inform. Process. Lett. 88(4) (2003) 155-159] in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2 - epsilon, instead, of of only 1 + root 5/2 approximate to 1.618 according to Peleg and Reshef [A variant of the arrow distributed directory with low average complexity, in: J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), ICALP, Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, 1999,pp.615-6241. (c) 2007 Elsevier B.V. All rights reserved.
机译：树扳手问题在网络设计中有重要的应用，例如在电信行业。在数学上，已经考虑了许多最大拉伸树扳手问题和平均拉伸树扳手问题。我们提出了20种树扳手问题的统一表示法，我们研究了具有一般正权重，公制权重和单位权重的图。这涵盖了组合优化的几个突出问题。有了这个符号，我们可以清楚地确定哪些问题是重合的。在未加权图的情况下，形式上有20个问题可以分解为只有五个不同的问题。此外，我们对树扳手问题的系统注释使我们能够识别到目前为止尚未解决复杂性状态的树扳手问题。我们能够提供NP硬度证明。此外，由于采用了新的树扳手问题表示法，因此我们能够检测到由于Galbiati [在最小-最大循环基础上，P。Eades，T。Takaoka（编辑），ISAAC，计算机科学讲义，第一卷。 2223，施普林格，柏林，2001年，第116-123页。在找到最大周期最短的周期基础和基本周期基础时，通知。处理。来吧88（4）（2003）155-159]实际上适用于经典的最大拉伸树扳手问题。因此，我们得出的结论是，根据Peleg和Reshef [此箭头分布目录的变体，其平均复杂度较低，在：J Wiedermann，P。van Emde Boas，M。Nielsen（编辑），ICALP，《计算机科学讲义》，第1卷。 1644年，施普林格，柏林，1999年，第615-6241页。 （c）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号