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

Fixed-parameter Tractable Algorithms for Weighted Matching and Packing Problems

作　　者：刘运龙[1] 陈建二[1] 王建新[1] 

机构地区：[1]中南大学信息科学与工程学院

出　　处：《小型微型计算机系统》2008年第4期672-677,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60433020)资助;新世纪优秀人才支持计划项目(NCET-05-0683)资助

摘　　要：带权的m-DMATCHING和m-SETPACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SETPACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法,接着在此基础上利用问题本身的结构特点对带权的m-DMATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SETPACKING问题和带权的m-DMATCHING问题都是固定参数可解的.The weighted m-D MATCHING and m-SET PACKING problems （m≥3） were solved by approximation algorithms in the past. In this paper, the parameterized versions of these problems are defined and their algorithms are studied. For the weighted m-SET PACKING problem, a parameterized algorithm of running time O^＊ （12.8^mk） is developed, which is based on the recently improved color-coding technology and dynamic programming. For the weighted m-D MATCHING problem, a more efficient parameterized algorithm of running time O^＊ （12.8^（m-1）k） is similarly presented through refining the techniques. It is concluded that the weighted m-D MATCHING and weighed m-SET PACKING problems are fixed-parameter tractable.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]