Advanced Search
    Li Shaohua, Feng Qilong, Wang Jianxin, and Chen Jianer. Kernelization for Weighted 3-Set Packing Problem[J]. Journal of Computer Research and Development, 2012, 49(8): 17811-786.
    Citation: Li Shaohua, Feng Qilong, Wang Jianxin, and Chen Jianer. Kernelization for Weighted 3-Set Packing Problem[J]. Journal of Computer Research and Development, 2012, 49(8): 17811-786.

    Kernelization for Weighted 3-Set Packing Problem

    • 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 27k\+3-36k\+2+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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return