TCS Journal 2011 Journal Article
Improved deterministic algorithms for weighted matching and packing problems
- Jianer Chen
- Qilong Feng
- Yang Liu
- Songjian Lu
- Jianxin Wang
Based on the method of ( n, k ) -universal sets, we present a deterministic parameterized algorithm for the weighted r d-matching problem with time complexity O ∗ ( 4 ( r − 1 ) k + o ( k ) ), improving the previous best upper bound O ∗ ( 4 r k + o ( k ) ). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O ∗ ( 1 6 k + o ( k ) ), improving the previous best result O ∗ ( 21. 2 6 k ). For the weighted r -set packing problem, we present a deterministic parameterized algorithm with time complexity O ∗ ( 2 ( 2 r − 1 ) k + o ( k ) ), improving the previous best result O ∗ ( 2 2 r k + o ( k ) ). The algorithm, when applied to the unweighted 3-set packing problem, has running time O ∗ ( 3 2 k + o ( k ) ), improving the previous best result O ∗ ( 43. 6 2 k + o ( k ) ). Moreover, for the weighted r -set packing and weighted r d-matching problems, we give a kernel of size O ( k r ), which is the first kernelization algorithm for the problems on weighted versions.