论文部分内容阅读
3-SetPacking参数化计数问题即在一个3-SetPacking实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]一难的，表明该问题不大可能存在固定参数可解的精确算法（除非#W[l]-FPT）。然后，通过拓展3-DMatching参数化计数问题的算法对3-SetPacking参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。