Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
An Improved Parameterized Algorithm for a Generalized Matching Problem
verfasst von : Jianxin Wang, Dan Ning, Qilong Feng, Jianer Chen
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 7
k
for the problem, improving the previous best kernel size 15
k
. The new kernelization leads to an improved algorithm for the problem with running time
O
*
(2
4.142
k
), improving the previous best algorithm of time
O
*
(2
5.301
k
).