Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems
Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems
复制标题
P2-Packing 和 Co-Path Packing 问题的随机参数化算法
DOI：
10.1007/s10878-013-9691-z
复制
发表时间：
2015
影响因子：
1
通讯作者：
Jianer Chen
中科院分区：
文献类型：
--
作者：
Qilong Feng;Jianxin Wang;Shaohua Li;Jianer Chen
本文从随机角度研究了参数化装箱问题和参数化共路装箱问题。对于参数化装箱问题，在问题结构分析的基础上，利用随机划分技术，得到了运行时间的随机参数化算法，改进了当前的最佳结果。对于参数化共路Packing问题，我们首先研究了度有界实例的核和随机化算法，其中实例中的每个顶点的度最多为3。给出了有界度约束的参数化共路Packing问题的核大小和运行时间的随机化算法。应用迭代压缩技术，在度有界问题随机化算法的基础上，给出了参数化共路装箱问题的一个运行时间随机化算法。
In this paper, we study the Parameterized-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running timeis obtained, improving the current best result. 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 sizeand a randomized algorithm of running timeare 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 timeis given for the Parameterized Co-Path Packing problem.