...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On packing and coloring hyperedges in a cycle
【24h】

On packing and coloring hyperedges in a cycle

机译：在循环中对超边缘进行包装和着色

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

摘要

Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link e(j) on the cycle is used at most c(j) times, each hyperedge hi has its profit pi and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC). In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit I and each link ej has same capacity k, we propose an algorithm with approximation ratio 3/2 (C) 2007 Elsevier B.V. All rights reserved.
机译：给定一个超图和k种不同的颜色，我们研究将超图的超边缘的子集打包并着色为一个循环中的路径的问题，以使所选超边缘的总利润最大化，其中每个物理链接该循环最多使用c（j）次，每个超边缘hi都有其获利pi，并且任何两条跨越其对应的超边缘的所有节点的路径，如果它们共享同一物理链路，则必须分配不同的颜色。这个新问题出现在光通信网络中，被称为在循环问题中对超边进行包装和着色时使利润最大化（MPPCHC）。在本文中，我们证明了MPPCHC问题是NP难问题，然后针对该问题提出了一种近似比为2的算法。对于每个超边具有相同利润I而每个链接ej具有相同容量k的特殊情况，我们提出一种算法，其近似比为3/2（C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号