Improved deterministic algorithms for weighted matching and packing problems Academic Article uri icon

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.

published proceedings

  • THEORETICAL COMPUTER SCIENCE

author list (cited authors)

  • Chen, J., Feng, Q., Liu, Y., Lu, S., & Wang, J.

citation count

  • 19

complete list of authors

  • Chen, Jianer||Feng, Qilong||Liu, Yang||Lu, Songjian||Wang, Jianxin

publication date

  • May 2011