Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems Academic Article uri icon

abstract

  • 2013, Springer Science+Business Media New York. In this paper, we study the Parameterized P2-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized P2-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running time O(6.75k) is obtained, improving the current best result O(8k). 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(2k) 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(3k) is given for the Parameterized Co-Path Packing problem.

published proceedings

  • Journal of Combinatorial Optimization

author list (cited authors)

  • Feng, Q., Wang, J., Li, S., & Chen, J.

citation count

  • 20

complete list of authors

  • Feng, Qilong||Wang, Jianxin||Li, Shaohua||Chen, Jianer

publication date

  • January 2015