Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems

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.

authors

• Chen, Jianer

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

publisher

• Springer Nature  Publisher

published in

• Journal of Combinatorial Optimization  Journal

keywords

• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4904 Pure Mathematics

Digital Object Identifier (DOI)

• 10.1007/s10878-013-9691-z

start page

• 125

end page

• 140

volume

• 29

issue

• 1

URL

• http://dx.doi.org/10.1007/s10878-013-9691-z