3-Set Packing参数化计数问题的复杂性及近似算法

摘要：

3-Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数.首先证明了该问题的计算复杂性是#w[I]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[l]=FPT).然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法.

关键词：3-Set Packing、计数、复杂性、近似算法

所属期刊栏目：43

分类号：TP301(计算技术、计算机技术)

在线出版日期：2016-10-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：23-26