• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Traffic Grooming in Star Networks via Matching Techniques
【24h】

Traffic Grooming in Star Networks via Matching Techniques

机译：通过匹配技术对星形网络中的流量进行梳理

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

摘要

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, it can be viewed as assigning colors to given paths in a graph, so that at most g (the grooming factor) paths of the same color can share an edge. Each path uses an ADM at each of its endpoints, and paths of the same color can share an ADM in a common endpoint. There are two sub-models, depending on whether or not paths that have the same color can use more than two edges incident with the same node (bifurcation allowed and bifurcation not allowed, resp.). The goal is to find a coloring that minimizes the total number of ADMs. In a previous work it was shown that the problem is NP-complete when bifurcation is allowed, even for a star network. In this paper we study the problem for a star network when bifurcation is not allowed. For the case of simple requests - in which only the case of g = 2 is of interest - we present a polynomial-time algorithm, and we study the structure of optimal solutions. We also present results for the case of multiple requests and g = 2, though the exact complexity of this case remains open. We provide two techniques, which lead to 4/3-approximation algorithms. Our algorithms reduce the problem of traffic grooming in star networks to several variants of maximum matching problems.
机译：修饰的问题是光网络研究的中心。用图论的术语来说，它可以看作是将颜色分配给图中的给定路径，因此相同颜色的g（修饰因子）路径最多可以共享一条边。每个路径在其每个端点处都使用一个ADM，并且相同颜色的路径可以在一个公共端点中共享一个ADM。有两个子模型，具体取决于具有相同颜色的路径是否可以使用与同一节点入射的两个以上的边（分别允许分支和不允许分支）。目的是找到使ADM总数最少的颜色。在先前的工作中表明，即使对于星形网络，允许分叉时问题也是NP完全的。在本文中，我们研究了不允许分叉时的星形网络问题。对于简单的请求-仅关注g = 2的情况-我们提出了多项式时间算法，并研究了最优解的结构。我们还给出了多个请求且g = 2的情况下的结果，尽管这种情况的确切复杂性仍然是未知的。我们提供了两种技术，可得出4/3逼近算法。我们的算法将星型网络中的流量疏导问题减少为最大匹配问题的几种变体。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号