An improved kernelization for P2-packing Academic Article uri icon

abstract

  • The P 2 -packing problem is a generalized matching problem and is known to be NP-hard. A kernelization algorithm for the parameterized P 2 -packing problem is a polynomial time algorithm that on an instance (G, k) of the problem produces another instance (G , k ) such that k k and that (G, k) is a yes-instance if and only if (G , k ) is a yes-instance. The graph G in the reduced instance is called a kernel. We provide new structural analysis and develop a new kernelization algorithm for the problem that produces a kernel of at most 7k vertices. This improves the previous best kernelization algorithm that produces a kernel of 15k vertices. Based on the new kernel, we present a parameterized algorithm of running time O * (17.66 k ) for the problem, improving the previous best upper bound O * (32 k ). 2009 Elsevier B.V.

published proceedings

  • Information Processing Letters

author list (cited authors)

  • Wang, J., Ning, D., Feng, Q., & Chen, J.

citation count

  • 20

complete list of authors

  • Wang, Jianxin||Ning, Dan||Feng, Qilong||Chen, Jianer

publication date

  • February 2010