Improved deterministic algorithms for weighted matching and packing problems
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O*(4(r-1)k+o(k)), improving the previous best upper bound O*(4rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O*(16k+o(k)), improving the previous best result O*(21.26k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O*(2(2r-1)k+o(k)), improving the previous best result O*(22rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O*(32k+o(k)), improving the previous best result O*(43.62k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(kr), which is the first kernelization algorithm for the problems on weighted versions. 2010 Elsevier B.V. All rights reserved.