欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
带权的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.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：