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

• 作者: 刘运龙
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 3-Set Packing 计数 复杂性 近似算法
• 年，卷（期）: 2016,（9）
• 页码范围: 23-26
• 页数: 4页
• 分类号: TP301
• 字数: 5719字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2016.9.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘运龙	湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室	15	34	3.0	5.0