• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Efficient algorithms for wavelength assignment on trees of rings
【24h】

Efficient algorithms for wavelength assignment on trees of rings

机译：在环树上进行波长分配的高效算法

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

摘要

A fundamental problem in communication networks is wavelength assignment (WA):given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree using at most 3L wavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L u pper bound is tight since there are instances of the WA problem that require 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation (resp. 2.5-approximation) algorithm for the WA problem on a tree of rings with degree at most six (resp. eight). Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).
机译：通信网络中的一个基本问题是波长分配（WA）：给定网络上的一组路由路径，将波长分配给每个路径，以便使用最小波长数将具有相同波长的路径边缘分离。对于树状环网络，WA问题是NP难题，在实践中使用得很好。在本文中，我们给出了一种有效的算法，该算法使用最多3L波长来解决具有任意（节点）度的环树上的WA问题，并且渐近地达到2.75的近似比，其中L是任何路径上的最大路径数网络中的链接。由于存在WA问题的实例，即使在四度的圆环树上，也需要3L的波长，因此3L的限制非常严格。我们还针对度数最大为6（分别为8）的圆环树上的WA问题，给出了3L和2近似（分别为2.5）的算法。先前的结果包括：具有任意度数（最多8度）的圆环树的4L（分别为3L）波长，以及具有度数4（最大6）的圆环树的2近似（大约2.5近似值）算法。 ）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号