计算机科学 ›› 2010, Vol. 37 ›› Issue (5): 210-213.
• 人工智能 • 上一篇 下一篇
刘运龙,王建新
出版日期:
发布日期:
基金资助:
LIU Yun-long,WANG Jian-xin
Online:
Published:
摘要： 枚举问题的多个最优解是计算机科学中人们日益关注的一个研究方向。运用固定参数枚举理论和着色技术对3一维匹配问题提出了一个高效的固定参数枚举算法，即给定一个含有n个带权值的元组集合S，两个非负整数k和z，该算法能在时间O(5. 483kkn2z)内枚举出S中权值最大的z个k-matchings，进而表明了3-维匹配问题是固定参数线性可枚举的。
关键词: 3-维匹配问题，固定参数枚举，着色技术
Abstract: 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.
Key words: 3-D Matching, Fixed-parameter enumerable, Color-coding
刘运龙,王建新. 3-维匹配问题的一种固定参数枚举算法[J]. 计算机科学, 2010, 37(5): 210-213. https://doi.org/
LIU Yun-long,WANG Jian-xin. Efficient Fixed-parameter Enumeration Algorithm for the 3-D Matching Problem[J]. Computer Science, 2010, 37(5): 210-213. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2010/V37/I5/210
Cited
首页