Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-Set Packing的核心化算法.对于加权3-Set Packing问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-Set Packing问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-Set Packing问题大小为27k3—36k2 +12k的核,该核心化结果是加权3-Set Packing问题的首个核心化结果.得到的加权3-Set Packing的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核.%Packing and Matching problems form an important class of NP-hard problems, which have attracted lots of attention in the study of parameterized algorithms and kernelization of the problems. In this paper, we mainly study the kernelization algorithm for weighted 3-Set Packing problem. By further analyzing the problem structure, this paper proposes and proves two reduction rules for the weighted 3-Set Packing problem. Firstly, the numbers of sets in given instance of weighted 3-Set Packing problem containing two fixed elements and containing only one element are bounded. Based on the two bounded numbers, the total number of sets in the instance is bounded. Moreover, the processes of getting the two bounded numbers bring two efficient reduction rules for the weighted 3-Set Packing problem. Applying the two reduction rules, a kernel of size 27k3-36k2 + 12k can be obtained, which is the first kernel result for weighted 3-Set Packing problem. The kernelization process for weighted 3-Set Packing problem can also be applied to the weighted 3D-Matching problem, which results in the same kernel size as that of the weighted 3-Set Packing problem.
展开▼
