一个基于着色和动态规划的3-维匹配问题算法

摘要：

3-维匹配问题是六个经典的NP完全问题之一,在调度、分配、交通和网络流等问题方面有很强的应用.参数计算理论是近年来发展起来的研究和解决NP-难问题的新方法.针对3-维匹配问题,目前确定式参数算法的最好结果是O*(163k).本文结合着色和动态规划技术,提出了一个算法运行时间为O*(3.423k)的确定式参数算法,大大提高了算法的运行效率.

关键词：3-维匹配、着色、动态规划

所属期刊栏目：34

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

资助基金：国家自然科学基金60433020

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

页数：共3页

页码：222-224