...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of combinatorial optimization >Randomized parameterized algorithms for P-2-Packing and Co-Path Packing problems
【24h】

Randomized parameterized algorithms for P-2-Packing and Co-Path Packing problems

机译：用于P-2-Packing和Co-Path Packing问题的随机参数化算法

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

摘要

In this paper, we study the Parameterized P-2-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized P-2-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running time O*(6.75(k)) is obtained, improving the current best result O*(8(k)). For the Parameterized Co-Path Packing problem, we firstly study the kernel and randomized algorithm for the degree-bounded instance, where each vertex in the instance has degree at most three. A kernel of size 20k and a randomized algorithm of running time O*(2(k)) are given for the Parameterized Co-Path Packing problem with bounded degree constraint. By applying iterative compression technique and based on the randomized algorithm for degree bounded problem, a randomized algorithm of running time O*(3(k)) is given for the Parameterized Co-Path Packing problem.
机译：在本文中，我们从随机的角度研究了参数化P-2-Packing问题和参数化Co-Path Packing问题。对于参数化P-2-Packing问题，基于问题的结构分析并使用随机分区技术，获得了运行时间O *（6.75（k））的随机参数化算法，从而改善了当前的最佳结果O *（ 8（k））。对于参数化共路径打包问题，我们首先研究度约束实例的内核和随机算法，其中实例中的每个顶点最多具有三个度。针对有界度约束的参数化共路径压缩问题，给出了大小为20k的内核和运行时间为O *（2（k））的随机算法。通过应用迭代压缩技术，并基于度界问题的随机算法，针对参数化共路径打包问题给出了运行时间O *（3（k））的随机算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号