...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Parameterized algorithms for weighted matching and packing problems
【24h】

Parameterized algorithms for weighted matching and packing problems

机译：加权匹配和打包问题的参数化算法

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

摘要

The weighted m-D MATCHING and m-SET PACKING problems (m >= 3) are usually solved through approximation algorithms. In this paper, we define the parameterized versions of these problems and study their algorithms. For the weighted m-SET PACKING problem, we develop a parameterized algorithm of running time 0(12.8(mk)n(0(1))), which is based on the recently improved color-coding technology and dynamic programming. By refining the techniques, we also develop a more efficient parameterized algorithm of running time 0(12.8((m-1)k)n(0(1))) for the weighted m-D MATCHING problem, which is a restricted version of the weighted m-SET PACKING problem.
机译：加权的m-D匹配和m-SET打包问题（m> = 3）通常通过近似算法来解决。在本文中，我们定义了这些问题的参数化版本并研究了它们的算法。对于加权的m-SET PACKING问题，我们基于最近改进的颜色编码技术和动态编程，开发了运行时间0（12.8（mk）n（0（1）））的参数化算法。通过完善技术，我们还针对加权mD匹配问题开发了更有效的运行时间0（12.8（（m-1）k）n（0（1）））的参数化算法，这是加权的受限版本m-SET PACKING问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号