计算机科学 ›› 2007, Vol. 34 ›› Issue (7): 222-224.
• 软件工程与数据库技术 • 上一篇 下一篇
宁丹 王建新
出版日期:
发布日期:
基金资助:
NING Dan ,WANG Jian-Xin （School of Information Science and Engineering, Central South University, Changsha 410083）
Online:
Published:
摘要： 摘要3-维匹配问题是六个经典的NP完全问题之一，在调度、分配、交通和网络流等问题方面有很强的应用。参数计算理论是近年来发展起来的研究和解决NP-难问题的新方法。针对3-维匹配问题，目前确定式参数算法的最好结果是O·（16^3k）。本文结合着色和动态规划技术，提出了一个算法运行时间为O·（3．42^3k强）的确定式参数算法，大大提高了算法的运行效率。
关键词: 3-维匹配 着色 动态规划
Abstract: 3-Dimensional Matching is one of the six classic NP-complete problems, which has extensive application in scheduling, assignment, transportation and network flow problem, etc. Parameterized computation theory is a recently developed new method to study an
Key words: 3-Dimensional matching, Color coding, Dynamic programming
宁丹 王建新. 一个基于着色和动态规划的3-维匹配问题算法[J]. 计算机科学, 2007, 34(7): 222-224. https://doi.org/
NING Dan ,WANG Jian-Xin （School of Information Science and Engineering, Central South University, Changsha 410083）. [J]. Computer Science, 2007, 34(7): 222-224. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2007/V34/I7/222
Cited
首页