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

Efficient Fixed-parameter Enumeration Algorithm for the 3-D Matching Problem

作　　者：刘运龙[1,2] 王建新[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]湖南师范大学继续教育学院,长沙410013

出　　处：《计算机科学》2010年第5期210-213,共4页Computer Science

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

摘　　要：枚举问题的多个最优解是计算机科学中人们日益关注的一个研究方向。运用固定参数枚举理论和着色技术对3-维匹配问题提出了一个高效的固定参数枚举算法,即给定一个含有n个带权值的元组集合S,两个非负整数k和z,该算法能在时间O(5.483kkn2z)内枚举出S中权值最大的z个k-matchings,进而表明了3-维匹配问题是固定参数线性可枚举的。Enumerating a number of good solutions to a problem has an increasing demand in recented research in computational science. In this paper, we presented a fixed-parameter enumeration algorithm for the 3-D Matching problem.More precisely, we developed an algorithm that, on a given set S of n weighted triples and two integers k and z, produces z ＂best＂ k-matchings in time O（5. 483kkn2z）. Our algorithm is based on the recent improved color-coding techniques and the fixed-parameter enumeration framework. This result shows that the 3-D Matching problem is fixed parameter linearly cnumcrablc.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]