带权Matching和Packing问题的一种固定参数可解算法

摘要：

带权的m-D MATCHING和m-SET PACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SET PACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法, 接着在此基础上利用问题本身的结构特点对带权的m-D MATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SET PACKING问题和带权的m-D MATCHING问题都是固定参数可解的.

关键词：带权m-SET PACKING、带权m-D MATCHING、着色、固定参数可解

所属期刊栏目：29

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60433020;教育部跨世纪优秀人才培养计划NCET-05-0683

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

页数：共6页

页码：672-677