3-维匹配问题的一种固定参数枚举算法

摘要：

枚举问题的多个最优解是计算机科学中人们日益关注的一个研究方向.运用固定参数枚举理论和着色技术对3-维匹配问题提出了一个高效的固定参数枚举算法,即给定一个含有n个带权值的元组集合S,两个非负整数k和z,该算法能在时间0(5.483kkn2z)内枚举出S中权值最大的z个k-matchings,进而表明了3-维匹配问题是固定参数线性可枚举的.

关键词：3-维匹配问题、固定参数枚举、着色技术

所属期刊栏目：37

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

资助基金：国家973前期研究专项课题"信息处理中的参数算法研究"2008CB317107;国家自然科学基金项目"参数计算理论及应用"60773111

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

页数：共4页

页码：210-213