An Improved Parameterized Algorithm for a Generalized Matching Problem
Jianxin Wang1 
, Dan Ning1, Qilong Feng1 and Jianer Chen1
| (1) |
School of Information Science and Engineering, Central South University, |
Abstract
We study the parameterized complexity of a generalized matching problem, the P
2-packing problem. The problem is NP-hard and has been studied by a number of researchers. In this paper, we provide further
study of the structures of the P
2-packing problem, and propose a new kernelization algorithm that produces a kernel of size 7k for the problem, improving the previous best kernel size 15k. The new kernelization leads to an improved algorithm for the problem with running time O
*(24.142 k
), improving the previous best algorithm of time O
*(25.301 k
).
This work is in part supported by the National Natural Science Foundation of China under Grant No. 60773111 and No. 60433020,
Provincial Natural Science Foundation of Hunan (06JJ10009), the Program for New Century Excellent Talents in University No.
NCET-05-0683 and the Program for Changjiang Scholars and Innovative Research Team in University No. IRT0661.
References secured to subscribers.