...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Multi-Level Steiner Trees
【24h】

Multi-Level Steiner Trees

机译：多级斯坦纳树

获取原文
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with non-negative edge costs and a set of terminals T subseteq V. The objective is to find a minimum-cost edge set E' subseteq E that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of rho = ln(4)+epsilon 1.39. In this paper, we study a natural generalization, the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals T_1 subset ... subset T_k subseteq V, compute nested edge sets E_1 subseteq ... subseteq E_k subseteq E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under names such as Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using four types of graph generators. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is small (k = 22), which works well for applications such as designing multi-level infrastructure or network visualization.
机译：在经典的Steiner树问题中，给定一个无向的连通图G =（V，E），具有非负边际成本和一组终端TsubseteqV。目标是找到最小成本边际集合E'横跨终端的subseteqE。这个问题很难解决。最著名的近似算法的比率为rho = ln（4）+ε<1.39。在本文中，我们研究自然归纳法，即多级斯坦纳树（MLST）问题：给定终端T_1子集... T_k子集子集V的嵌套序列，计算嵌套边集E_1子集eq ...子集E_k子集E以最小的总成本跨越相应的终端机。已经以诸如服务质量组播树，服务等级斯坦纳树和多层树之类的名称研究了MLST问题及其变体。几种近似结果是已知的。我们首先提出两种自然启发法，其近似因子为O（k）。基于这些，我们介绍了一种需要2 ^ k Steiner树计算的复合算法。我们通过求解线性程序来确定其近似比率。然后，我们提出一种方法，该方法可以保证近似比率相同，并且最多需要2k Steiner树计算。我们使用四种类型的图形生成器在几种类别的图形上实验比较了五种算法。我们还为MLST实现了整数线性程序，以提供基本信息。当级别数很少时（k <= 22），我们的组合算法在理论上和实践上都比其他算法好，这在诸如设计多层基础结构或网络可视化的应用中效果很好。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号